006 · Merge Two Sorted Lists

algorithm
Published

April 22, 2026

My First Thoughts

这道题一开始最不舒服的地方，不是“怎么合并”，而是题目里的词：

  • 链表，linked list
  • 节点，node
  • 头节点，head

如果之前主要接触的是 array 或 Python 的 list，那看到 list1 = [1,2,4] 很容易以为输入就是一个普通列表。

但在这道题里，[1,2,4] 只是题目为了展示方便写出来的样子。真实结构更像这样：

list1
  |
  v
[1] -> [2] -> [4] -> None

每个节点 node 里有两样东西：

node.val   当前节点的值
node.next  下一个节点

所以 head 是指链表的第一个节点。

只要拿到第一个节点，就可以一路通过 .next 走到后面：

head -> node -> node -> node -> None

理解到这里以后，这题的直觉其实很自然：

两个链表都已经排好序了，那就每次比较两个当前节点，谁小就先拿谁。

比如：

list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

先比较两个开头的 1，拿一个较小的；然后被拿走的那条链表往后走一步。接着继续比较当前两个节点。

这个思路可以先写成更接近代码的形式：

def merge(list1, list2):
    if list1.val <= list2.val:
        first = list1
        list1 = list1.next
    else:
        first = list2
        list2 = list2.next

    return first

这段还不是完整答案，但它已经抓住了正确方向：

  • 比较 list1.val 和 list2.val
  • 选出较小的那个节点
  • 被选中的那条链表往后走一步

这里有一个重要写法：

list1 = list1.next

这句话的意思是：现在 list1 不再指向原来的节点，而是指向下一个节点。

也就是说，链表题里很多变量不是在“保存一个值”，而是在“指向一个节点”。让变量等于 .next，就是让它沿着链表往后移动。

Why That Is Not Enough

如果只写“谁小就拿谁”，还差一个很具体的问题：

拿出来的节点，要接到哪里？

我们需要维护一个结果链表。更准确地说，需要知道结果链表当前的最后一个节点在哪里。

这个“最后一个节点”通常叫 tail。

result: 1 -> 1 -> 2
                  ^
                  tail

当我们决定把某个节点接进结果链表时，就做两步：

tail.next = list1
tail = tail.next

第一行：

tail.next = list1

意思是：把 list1 当前指向的节点，接到结果链表的最后面。

第二行：

tail = tail.next

意思是：结果链表变长了，所以 tail 也要移动到新的最后一个节点。

然后，因为 list1 当前节点已经被接走了，list1 自己也要往后走：

list1 = list1.next

所以核心循环大概是：

if list1.val <= list2.val:
    tail.next = list1
    list1 = list1.next
else:
    tail.next = list2
    list2 = list2.next

tail = tail.next

这里还有一个边界麻烦：结果链表一开始是空的，那第一个节点怎么接？

如果没有任何辅助做法，就要单独判断：

如果结果链表还没有头节点，就先设置 head
否则才接到 tail.next

这会让代码里多出很多“第一次”的特殊处理。

这就是 dummy node 出现的原因。

dummy 可以翻译成“虚拟节点”或“哑节点”。它是一个临时放在最前面的假节点，不属于最终答案。

dummy -> None
tail
  |
  v
dummy

有了它以后，结果链表从一开始就有一个固定起点。我们每次都可以统一写：

tail.next = 某个节点
tail = tail.next

不需要再单独处理“第一个节点是谁”。

最后真正的答案不是 dummy，而是 dummy.next：

dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4
          ^
          这才是真正的 head

Final Idea

创建一个 dummy 节点作为临时起点，再用 tail 指向结果链表当前的最后一个节点。

然后同时遍历 list1 和 list2：

  1. 比较 list1.val 和 list2.val。
  2. 谁更小，就把谁当前的 node 接到 tail.next。
  3. 被接走的那条链表往后走一步。
  4. tail 也往后走一步。

当其中一个链表走到 None 时，说明它已经用完了。

因为两个链表本来就是升序的，所以另一个链表剩下的部分不需要再一个个比较，可以直接接到 tail.next。

Why It Works

每一步我们都只比较两个链表当前还没有合并的最小节点。

因为 list1 和 list2 本身都是升序排列，所以：

  • list1 当前节点是 list1 剩余部分里最小的
  • list2 当前节点是 list2 剩余部分里最小的

两者中较小的那个，一定就是整个剩余部分里最应该先放进结果链表的节点。

接完这个节点后，对应链表往后走，继续处理下一个候选节点。

当某一条链表为空时，另一条链表剩下的节点已经排好序，直接接上不会破坏整体顺序。

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next

            tail = tail.next

        if list1:
            tail.next = list1
        else:
            tail.next = list2

        return dummy.next

Complexity

Time \(O(m+n)\) — 两个链表的每个节点最多被走过一次
Space \(O(1)\) — 只用了 dummy 和 tail 这些额外指针，没有新建一整个链表

Takeaway

链表题里，变量经常不是“保存值”，而是“指向某个节点”。list1 = list1.next 表示让指针往后走；tail.next = list1 表示把一个节点接到结果链表后面。dummy node 的作用只是把“第一个节点怎么处理”这个边界问题变简单，最后返回真正的头节点 dummy.next。

← Quiz