题解 | 合并两个排序的链表

描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

算法

比较方便的做法是设置一个虚拟节点 fake，而它的 next 指向的地址才是真正的表头，然后开始的时候将它作为 pre 指针。在循环中，每次都将要接入的新节点接到 pre 后面，然后更新 pre，保持这个循环不变式。

最后返回 fake 的 next 指向的地址，就是完整的结果。

// c++
class Solution {
public:
    ListNode* Merge(ListNode* p1, ListNode* p2) {
        ListNode* fake = new ListNode(0), *pre = fake;
        while (p1 && p2) {
            if (p1->val < p2->val) pre->next = p1, p1 = p1->next; // p1的节点值小就将p1接入要返回的链表
            else pre->next = p2, p2 = p2->next; // p2 节点值小于等于p1就将p2 接入返回的链表
            pre = pre->next;
        }
        // 此时至少有一个链表已经完全遍历
        while (p1) pre->next = p1, p1 = p1->next, pre = pre->next; // 处理没有完全遍历的 p1
        while (p2) pre->next = p2, p2 = p2->next, pre = pre->next; // 处理没有完全遍历的 p2
        return fake->next;
    }
};

# python3
class Solution:
    def Merge(self, p1, p2):
        fake = ListNode(0)
        pre = fake
        while p1 and p2:
            if p1.val <= p2.val:
                pre.next = p1 # p1的节点值小就将p1接入要返回的链表
                p1 = p1.next # p2 节点值小于等于p1就将p2 接入返回的链表
            else:
                pre.next = p2
                p2 = p2.next
            pre = pre.next
        while p1:
            pre.next = p1
            p1 = p1.next
            pre = pre.next
        while p2:
            pre.next = p2
            p2 = p2.next
            pre = pre.next
        return fake.next

时间复杂度是 O(m + n)，空间复杂度是 O(1)

链表循环另一种比较简短的写法

// c++
class Solution {
public:
    ListNode* Merge(ListNode* p1, ListNode* p2) {
        ListNode* fake = new ListNode(0), *pre = fake;
        while (p1 || p2) {
            if (!p2 || (p1 && p1->val <= p2->val))
                pre->next = p1, p1 = p1->next; // 当 p2 已经结束或者 p1 的值更小就接入 p1
            else if (!p1 || (p2 && p1->val > p2->val))
                pre->next = p2, p2 = p2->next; // 当 p1 已经结束或者 p1 的值没有更小就接入 p2
            pre = pre->next;
        }
        return fake->next;
    }
};

# python3
class Solution:
    def Merge(self, p1, p2):
        fake = ListNode(0)
        pre = fake
        while p1 or p2:
            if (not p2) or (p1 and p1.val <= p2.val): 
                pre.next = p1 # 当 p2 已经结束或者 p1 的值更小就接入 p1
                p1 = p1.next
            elif (not p1) or (p2 and p1.val > p2.val): 
                pre.next = p2 # 当 p1 已经结束或者 p1 的值没有更小就接入 p2
                p2 = p2.next
            pre = pre.next
        return fake.next

因为每个链表循环了一次，所以时间复杂度是 O(m + n)，m 和 n 分别是两个链表的长度，空间复杂度是 O(1)。