首页 > 其他 > 详细

将两个有序链表合并,合并后仍然有序

时间:2018-09-25 12:27:06      阅读:107      评论:0      收藏:0      [点我收藏+]

 

思路:因为A,B链表中元素有序,要使归并后的C也有序,可以每次从A、B中挑出最小的元素插入C的尾部,这样循环插入完成后,C也一定是有序的。

 1 struct LinkList{
 2     int data;
 3     LinkList *next;
 4 }
 5 
 6 void Merge(LinkList *A,LinkList *B,LinkList *&C)
 7 {
 8     LinkList *p = A->next;    // 定义p结点跟踪 A中的结点
 9     LinkList *q = B->next;    // 定义q结点跟踪 B中的结点
10 
11     C = A;
12     C->next = NULL;
13     free(B);
14     
15     LinkList *r = C;   //  定义一个跟踪结点,永远指向C的终端结点
16     
17     while(p!=NULL&&q!=NULL){
18         if(p->data <= q->data){
19             r->next = p;
20             p = p->next;
21             r = r->next;
22         }else{
23             r->next = q;
24             q = q->next;
25             r = r->next;
26         }
27     }
28 
29     if(p!=NULL) r->next = p;
30     if(q!=NULL) r->next = q;
31 }

 

将两个有序链表合并,合并后仍然有序

原文:https://www.cnblogs.com/ll-10/p/9698815.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!