合并两个有序链表 | 秋招知识库

方法一：迭代（尾插法）

前置知识

思路

创建一个哨兵节点，作为合并后的新链表头节点的前一个节点。这样可以避免单独处理头节点，也无需特判链表为空的情况，从而简化代码。

比较 ${list}_{1}$ 和 ${list}_{2}$ 的节点值，如果 ${list}_{1}$ 的节点值小，则把 ${list}_{1}$ 加到新链表的末尾，然后把 ${list}_{1}$ 替换成它的下一个节点。如果 ${list}_{2}$ 的节点值小则同理。如果两个节点值一样，那么把谁加到新链表的末尾都是一样的，不妨规定把 ${list}_{2}$ 加到新链表末尾。

重复上述过程，直到其中一个链表为空。

循环结束后，其中一个链表可能还有剩余的节点，将剩余部分加到新链表的末尾。

最后，返回新链表的头节点，即哨兵节点的下一个节点。

Python 解法1C++ 解法1

python

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1  # 把 list1 加到新链表中
                list1 = list1.next
            else:  # 注：相等的情况加哪个节点都是可以的
                cur.next = list2  # 把 list2 加到新链表中
                list2 = list2.next
            cur = cur.next
        cur.next = list1 or list2  # 拼接剩余链表
        return dummy.next

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy; // 用哨兵节点简化代码逻辑
        ListNode* cur = &dummy; // cur 指向新链表的末尾
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1; // 把 list1 加到新链表中
                list1 = list1->next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur->next = list2; // 把 list2 加到新链表中
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }
};

复杂度分析

时间复杂度： $O (n + m)$ ，其中 $n$ 为 ${list}_{1}$ 的长度， $m$ 为 ${list}_{2}$ 的长度。
空间复杂度： $O (1)$ 。仅用到若干额外变量。

方法二：递归（头插法）

前置知识

如何理解递归？计算机是怎么执行递归的？【基础算法精讲 09】

思路

直接把 mergeTwoLists 当作递归函数：

递归边界：如果其中一个链表为空，直接返回另一个链表作为合并后的结果。
如果两个链表都不为空，则比较两个链表当前节点的值，选择较小的节点插在前面。
- 如果 ${list}_{1}$ 的节点值更小，那么取出 ${list}_{1}$ ，递归调用 mergeTwoLists(list1.next, list2)，拿到递归返回的链表，把 ${list}_{1}$ 插在前面。
- 如果 ${list}_{2}$ 的节点值更小，那么取出 ${list}_{2}$ ，递归调用 mergeTwoLists(list1, list2.next)，拿到递归返回的链表，把 ${list}_{2}$ 插在前面。

Python 解法3C++ 解法3

python

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None: return list2  # 注：如果都为空则返回空
        if list2 is None: return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2; // 注：如果都为空则返回空
        if (list2 == nullptr) return list1;
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
};

复杂度分析

时间复杂度： $O (n + m)$ ，其中 $n$ 为 ${list}_{1}$ 的长度， $m$ 为 ${list}_{2}$ 的长度。
空间复杂度： $O (n + m)$ 。递归需要 $O (n + m)$ 的栈空间。

思考题

如果只保留两个有序链表中的相同元素（求交集），要怎么做？注意，如果第一个链表有 $3$ 个 $1$ ，第二个链表有 $2$ 个 $1$ ，那么答案链表中有 $2$ 个 $1$ 。

欢迎在评论区发表你的思路/代码。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：迭代（尾插法） ​

前置知识 ​

思路 ​

复杂度分析 ​

方法二：递归（头插法） ​

前置知识 ​

思路 ​

复杂度分析 ​

思考题 ​

分类题单 ​

方法一：迭代（尾插法）

前置知识

思路

复杂度分析

方法二：递归（头插法）

前置知识

思路

复杂度分析

思考题

分类题单