如何将两个有序链表并为一个有序链表

xuzwg

假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，现要归并La和Lb得到单链表Lc，按照算法MergeList的思想，需设立3个指针pa、pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点，若pa->data≤pb->data，则将pa所指向结点之后，否则将pb所指向结点链接到pc所指结点之后。显然，指针的初始状态为：当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度为隐含的，则第一个循环执行的条件时pa和pb皆非空，当其中一个为空时，说明有一个表的元素已归并完，则只要将另一个表的剩余段链接在pc所指结点之后即可。由此得到归并两个单链表的算法。
voidMergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc,){
* }( n9 |. D% _1 Z//已知单链线性表La和Lb的元素按值非递减排列。
/ e5 v. \, a* p//归并La和Lb得到新的单链线性表Lc，Lc的元素也按非递减排列。
pa=La->next;pb=Lb->next;
Lc=pc=La;           //用La的头结点作为Lc的头结点
  f- M2 l+ k- H# ]1 w3 t0 h7 rwhile(pa&&pb){
; k- @' P' G' k' N) H  W$ F" C5 ?4 uif(pa->data<=pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}
5 U, @- ]( j' E8 jelse{pc->next=pb;pc=pb;pb=pb->next;}
7 m: A& q" c- b/ s7 Q! K  s+ `2 C8 Y}
4 p& r  N- N8 S# d! R- C6 }" \pc->next=pa?=pa:pb;//插入剩余段
free(Lb);       //释放Lb的头结点
  j- [4 f' L6 H& h, c! Y0 t}//MergeList_L

cyxs

学习中，谢谢分享
7 [) P$ R- d* c9 _/ b

Gegu

谢谢O(∩_∩)O哈哈~谢谢O(∩_∩)O哈哈

duzy

谢谢楼主，一步步来，学习中……
( e( y$ R9 e/ }, a( z9 U