合并两个有序链表 图解题解

这道题真正在问什么

给两条各自升序的链表，把它们合并成一条仍然升序的链表并返回头节点。注意合并是「拼接原有节点」而不是「新造一条链」——理想做法应该只改各节点的 next 指向，不额外分配节点，这决定了空间可以做到 O(1)。

为什么每次只比较两个头就够了

问题的核心观察来自「各自有序」：任何时刻，所有还没被接走的节点里，全局最小的那个必然是两条链当前头节点之一。因为每条链内部越往后值越大，头就是各自的最小者，两个最小者再比一次，赢家就是全局最小。

把这个赢家接到结果尾部之后，剩下的局面仍然是「两条升序链表」——和原问题一模一样，只是规模少了一个节点。于是同一个判断可以一直重复下去，这正是归并排序里合并两个有序序列的经典操作。每一步都取当前能取的最小值，接出来的链自然从小到大，正确性不需要任何回头检查。

哑结点解决了什么问题

结果链表的头节点是谁，要等第一次比较之后才知道，可能来自任何一条链。不用哑结点的话，就得先单独比较一次、处理各种空链特判，才能把头定下来，代码立刻多出好几个分支。

哑结点（dummy）的做法是先放一个不存数据的占位节点，让尾指针 tail 从它出发，接第一个节点和接后面任何节点的动作完全一样：tail.next 指向被选中的节点，tail 前移。最后返回 dummy.next，占位节点自动被跳过。一个空节点换掉所有头部特判，这就是链表题里 dummy 反复出现的原因。

一条链走空后为什么能整段直接接上

循环条件是两条链都非空，所以必有一条先耗尽。此时剩下那条链上的每个节点都在之前的比较中「输」给过已接走的节点，也就是不小于结果链的最后一个值；而它内部本来就有序。两个条件合起来，整段原样接到尾部就是正确的升序，不需要再逐个比较。

这一步对应代码里的 tail.next = l1 if l1 else l2，忘写它是这道题最高频的 bug：一条链空了循环退出，另一条还挂着一整段没接，结果直接少一半数据。

复杂度与两个细节

时间 O(m+n)：每个节点恰好被比较有限次、接入一次，两条链各扫一遍。空间 O(1)：只用 dummy 和 tail 两个额外指针，节点全部复用。

细节一：两头相等时固定取第一条链的节点，保证排序稳定，也省一次多余判断。细节二：这套归并是合并 K 个升序链表（LeetCode 23）的基础——K 条链两两分治合并，或用小根堆每次弹出最小头，整体 O(N log K)，其中每一次基本合并用的都是本题的写法。

Python

def mergeTwoLists(l1, l2):
    dummy = tail = ListNode()   # 哑结点 + 尾指针
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1; l1 = l1.next
        else:
            tail.next = l2; l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2   # 接上剩余
    return dummy.next

C++

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
    ListNode dummy, *tail = &dummy;
    while(l1 && l2){
        if(l1->val <= l2->val){ tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

Java

public ListNode mergeTwoLists(ListNode l1, ListNode l2){
    ListNode dummy = new ListNode(0), tail = dummy;
    while(l1 != null && l2 != null){
        if(l1.val <= l2.val){ tail.next = l1; l1 = l1.next; }
        else { tail.next = l2; l2 = l2.next; }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}