IT评测·应用市场-qidao123.com技术社区

标题: 算法：两个升序单链表的合并 [打印本页]

---

作者: 涛声依旧在    时间: 2025-1-7 16:13
标题: 算法：两个升序单链表的合并
将两个按值排序的带头结点的单链表La和Lb分列成一个升序的
单链表，并返回一个新的单链表的表头指针
（两个升序合并成升序，用尾插法）

1. LinkList Merge_LinkList(LNode* La, LNode* Lb)
2. {
3.         //准备工作
4.         LNode* Lc;//新链表的头结点
5.         LNode* pc;//新链表的工作指针
6.         LNode* pa;//La的工作指针
7.         LNode* pb;//Lb的工作指针
8.         LNode* ptr;//用于删除结点时保存指针
9.         Lc = La;//Lc用La的头结点
10.         pc = La;//pc用于尾指针
11.         pa = La->next;//工作指针初始化
12.         pb = Lb->next;//工作指针初始化
13.        
14.         //合并
15.         while (pa != NULL && pb != NULL)
16.         {
17.                 if (pa->data < pb->data)
18.                 {
19.                         pc->next = pa;
20.                         pc = pa;//pa尾插
21.                         pa = pa->next;//pa后移
22.                 }
23.                 else if (pa->data > pb->data)
24.                 {
25.                         pc->next = pb;
26.                         pc = pb;//pb尾插
27.                         pb = pb->next;//pb后移
28.                 }
29.                 else//相等
30.                 {
31.                         pc->next = pa;
32.                         pc = pa;//二者插一个即可
33.                         pa = pa->next;//后移
34.                         ptr = pb;
35.                         pb = pb->next;//将另一个删除
36.                         free(ptr);
37.                 }
38.         }
39.         if (pa != NULL)//pa不空
40.                 pc->next = pa;//将pa接到pc的后继结点
41.         if (pb != NULL)
42.                 pc->next = pb;
43.         free(Lb);//释放Lb链表
44.         return Lc;
45. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4