【链表OJ题(五)】合并两个有序链表

​

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

上一篇链表OJ题链接：【链表OJ题(四)】反转链表

链表OJ题(五)

1. 合并两个有序链表

链接：21. 合并两个有序链表

描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例2：
输入：l1 = [], l2 = []
输出：[]
示例3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

1.1 思路–带哨兵位的头结点

之前做过一道题目，叫做合并两个有序数组。其中有一种方法是创建一个新数组，然后遍历两个数组，将两个数组的较小的元素放置到新数组中。一个数组遍历完，将没有放置的元素放置到新数组中，然后拷贝回原数组。

那么这道题能否借鉴它的思路？
合并两个有序链表，链表和数组不同，数组形式的一种方法需要我们创建一个新数组。但是对于链表而言我们可以通过指针改变链接关系，所以不需要创建新链表，只需要修改即可。
有序数组的做法是将较小元素逐个尾插到新数组中，那么我们也可以将较小元素尾插到链表中。

那么链表为空如何处理？
这时就又要用到哨兵位(头结点)了，我们给一个哨兵位 head，它也不存储数据，那么不就可以了？但是注意有效数据从 head->next 开始。

但是尾插存在两个问题，当尾插的时候，我们需要找链表的尾，而且当链表为空时，需要特殊处理。为了避免每次找链表的尾，那么我们就给定一个 tail，这样只要将 tail 迭代就可以。

注意：哨兵位需要释放，否则会造成内存泄漏。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head = NULL, *tail = NULL;if (list1 == NULL){return list2;} if (list2 == NULL){return list1;}// 哨兵位// 这里 tail 也需要动态开辟一下// 因为不在迭代时进行第一次插入的处理// tail 一开始为空指针，会报错head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));   while (list1 && list2){if (list1->val < list2->val){tail->next = list1; // 当前结点链表的尾链接到 list1tail = list1; // 链表的尾变成 list1list1 = list1->next; // list1 并没有改变，list1 迭代到list1的下一个节点}else{tail->next = list2;tail = list2;list2 = list2->next;}}// 未放置完的元素// 这里和数组的完全不一样// 链表是串联的，所以只需要把当前节点给到tail->next// 就可以全部串联if (list1){tail->next = list1;}if (list2){tail->next = list2;}// 释放哨兵位struct ListNode* ans = head->next;free(head); return ans;
}

1.2 思路–不强行加头结点

这道题目不使用哨兵位也能写，但是使用这种方法时，需要处理一下链表第一次合并时尾插的情况，大体思路和带哨兵位差不多，但需要注意一下细节

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode *head, *tail;head = tail = NULL;while (list1 && list2){if (list1->val < list2->val){// 第一次合并if (tail == NULL){head = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{// 第一次合并if (tail == NULL){head = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}if (list1)tail->next = list1;if (list2)tail->next = list2;return head;
}

2.总结：

今天我们通过两种思路分析并完成合并两个有序链表这道链表OJ题目，也更加深层次了解和使用了带哨兵位的头结点这个思路，在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~