拿捏链表（五）—— 合并两个有序链表

拿捏链表（五）—— 合并两个有序链表

文章目录

​​题目描述​​​​思路​​​​代码实现​​

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。（​​题目来源​​）

思路

该题的思路比较简单，我们只需创建一个头结点，然后从两个链表的表头开始依次比较传入的两个链表的结点的大小，并将两个链表中较小的结点尾插到新链表的后面即可。

完成一次尾插后，接着比较未尾插的结点，并将较小的结点继续尾插到新链表后面。

直到最后两个链表的结点都被尾插到新链表的后面。

注意两点：

1.在尾插过程中，若某一链表已被遍历完毕，则直接将另一个未遍历完的链表剩下的结点尾插到新链表后面即可。

2.函数返回的时候，不是返回头结点的地址，而是第一个结点的地址，所以我们要返回头结点指向的位置并将头结点释放。

代码实现

struct ListNode { int val; struct ListNode *next;};struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));//申请一个头结点 struct ListNode* tail = guard;//尾指针 struct ListNode* cur1 = l1;//记录当前遍历到的l1链表的结点位置 struct ListNode* cur2 = l2;//记录当前遍历到的l2链表的结点位置 while (cur1&&cur2)//当l1，l2中有一个链表遍历完毕时便停止 { //取小的结点尾插到新链表后面 if (cur1->val < cur2->val) { tail->next = cur1; cur1 = cur1->next; } else { tail->next = cur2; cur2 = cur2->next; } tail = tail->next;//结点增加，尾指针后移 } //将未遍历完的链表的剩余结点接到新链表后面 if (cur1) tail->next = cur1; else tail->next = cur2; struct ListNode* head = guard->next;//新链表的头指针 free(guard);//释放头结点 return head;//返回新链表}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。