链表是有序的，如何快速合并呢？
大家好，我是来自于华为的程序员小熊。今天给大家带来一道链表相关的题目，这道题同时也是字节、腾讯、亚马逊和微软等大厂的面试题，即力扣上的第21题-合并两个有序链表。
本文主要介绍递归和迭代两种策略来解答此题，供大家参考，希望对大家有所帮助。
合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
示例1
示例及提示
解题思路
要想将两个升序链表合并成一个新的升序链表，比较容易想到通过递归去实现。
方法一：递归
采用递归的主要思路
假设链表分别为 A 和 B，先比较 A 和 B 的头节点的值的大小，选择头节点值较小者（假设为 A）作为新的链表的头节点；然后再比较 A 的第二个节点的值与 B 的头节点的值的大小关系，选择较小者作为新链表的第二个节点；依次类推找出新链表的第三个节点...
❝递归终止条件：两链表一个为空时，结束递归。 ❞
Show me the Code
C
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
/* 两个链表其中一个为空，递归结束 */
if(l1 == NULL || l2 == NULL) {
return l1 == NULL ? l2 : l1;
}
/* 其中一个链表的头节点的值小于另一个，则选值较小者作为新链表头节点 */
if(l1->val < l2->val) {
/* 将该链表的剩余部分（子链表）跟另一个合并 */
l1->next = mergeTwoLists(l1->next,l2);
return l1;
} else {
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
C++
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr || l2 == nullptr) {
return l1 == nullptr ? l2 : l1;
}
if(l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next,l2);
return l1;
} else {
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
Java
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next,l2);
return l1;
} else {
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
Python3
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None or l2 is None:
return l2 if l1 is None else l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next = self.mergeTwoLists(l1,l2.next);
return l2;
Golang
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
} else if l2 == nil {
return l1
}
if l1.Val < l2.Val {
l1.Next = mergeTwoLists(l1.Next, l2)
return l1
} else {
l2.Next = mergeTwoLists(l1, l2.Next)
return l2
}
}
复杂度分析
时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度，需要递归调用两个链表的每个节点一次。
空间复杂度：O(n + m)。
方法二：迭代
除了采用递归外，还可以采用迭代的方法，具体如何操作，如下例子所示：
举例
以链表l1: 1->4->null 和链表l2: 2->3->null 为例。
例子
设置两个指针 cur1 和 cur2，分别指向两个链表的头节点；
设置指针
比较 cur1 和 cur2 指向的节点的值的大小，右移指向的节点值较小的 cur1；
比较节点值大小，并移动节点值较小的指针
设置一个指针 pre1，记录上次比较时值较小的节点；
设置一个节点，记录上一步右移前其指向的节点
设置一个指针 next，记录 cur2 指向节点的下一节点；
记录 cur2 下一节点
由于 pre1 指向的节点值小于 cur2 指向的节点值，连接它们；
新链表的头节点与第二个节点连接
同时由于 cur2 指向的节点小于 cur1 指向的节点，连接它们；
连接新链表
右移 pre1 和 cur2 分别到 cur2 和 next 位置；
移动指针
由于 cur1 指向的节点值大于 cur2 指向的节点值，将 pre1 指向的节点连接 cur2 指向的节点；
比较判断，重新获取第三个节点
由于 cur2 指向的节点值小于 cur1 指向的节点值，连接它们；
获取新链表的第四个节点
采用迭代法，合并两个上升链表到一个的完整过程，如下动图示：
迭代法的完整操作过程
Show me the Code
C
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if (l1 == NULL || l2 == NULL) {
return l1 != NULL ? l1 : l2;
}
struct ListNode* mergeHead = l1->val > l2->val ? l2 : l1;
struct ListNode* cur1 = mergeHead == l1 ? l1 : l2;
struct ListNode* cur2 = mergeHead == l1 ? l2 : l1;
/* 记录上次比较时节点值小的节点 */
struct ListNode* pre = NULL;
/* 记录当前节点值大的节点的下一节点 */
struct ListNode* next = NULL;
while (cur1 != NULL && cur2 != NULL) {
if (cur1->val <= cur2->val) {
pre = cur1;
cur1 = cur1->next;
} else {
next = cur2->next;
/* 将值较小的节点连接到另一链表节点值大的节点 */
pre->next = cur2;
/* 将另一链表中节点值大的节点连接到值较小的节点的下一节点 */
cur2->next = cur1;
pre = cur2;
cur2 = next;
}
}
/* 合并后 l1 和 l2 最多有一个未被合并完，链表末尾指向未合并完的链表 */
pre->next = cur1 == NULL ? cur2 : cur1;
return mergeHead;
}
C++
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr || l2 == nullptr) {
return l1 != nullptr ? l1 : l2;
}
ListNode* pre = nullptr;
ListNode* next = nullptr;
ListNode* mergeHead = l1->val > l2->val ? l2 : l1;
ListNode* cur1 = mergeHead == l1 ? l1 : l2;
ListNode* cur2 = mergeHead == l1 ? l2 : l1;
while (cur1 != nullptr && cur2 != nullptr) {
if (cur1->val <= cur2->val) {
pre = cur1;
cur1 = cur1->next;
} else {
next = cur2->next;
pre->next = cur2;
cur2->next = cur1;
pre = cur2;
cur2 = next;
}
}
pre->next = cur1 == nullptr ? cur2 : cur1;
return mergeHead;
}
Java
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 != null ? l1 : l2;
}
ListNode pre = null;
ListNode next = null;
ListNode mergeHead = l1.val > l2.val ? l2 : l1;
ListNode cur1 = mergeHead == l1 ? l1 : l2;
ListNode cur2 = mergeHead == l1 ? l2 : l1;
while (cur1 != null && cur2 != null) {
if (cur1.val <= cur2.val) {
pre = cur1;
cur1 = cur1.next;
} else {
next = cur2.next;
pre.next = cur2;
cur2.next = cur1;
pre = cur2;
cur2 = next;
}
}
pre.next = cur1 == null ? cur2 : cur1;
return mergeHead;
}
复杂度分析
时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度，需要遍历两个链表的每个节点。
空间复杂度：O(1)，未开辟额外空间。