---
title: "21. Merge Two Sorted Lists"
url: "https://laigary.com/interview/coding/21-merge-two-sorted-lists"
type: "note"
section: "coding"
date: "2024-06-09"
updated: "2026-07-29"
tags: ["Linked List", "Two Pointers"]
---

# 21. Merge Two Sorted Lists

[21\. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)

給兩個已排序的鏈結串列，合併成一個仍然排序的串列。要求接原本的節點，不是建新的。

## 思路

這就是**合併排序（merge sort）最後那一步**單獨拿出來考。兩個串列都已排序，所以只要比較兩顆頭，把小的那顆接到結果後面，然後那一邊往前走一步。重複到其中一邊走完為止。

真正的難點不在演算法，在**寫起來很容易被邊界搞爛**：

- 結果串列的「第一顆」要特別處理嗎？
- 其中一邊先走完了怎麼辦？
- 有一邊一開始就是空的怎麼辦？

第一個問題的標準解法是 **dummy head（[哨兵](/interview/coding/python-tips-for-interview)節點）**：先造一顆假的頭節點，所有接續動作都變成「接在某個已存在的節點後面」，完全不需要為第一顆寫特例。最後回傳 `dummy.next` 就是真正的頭。

這個手法在鏈結串列題幾乎是無腦必用的，見 [Linked List 模板](/interview/coding/linked-list-template)。

第二、三個問題其實是同一件事：**跳出迴圈時，最多只有一邊還有剩，而且它本身已經排序好了** —— 所以不需要逐顆搬，直接把整條接上去就行。

## 解題方向

```python
# 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]:
        h1 = list1
        h2 = list2

        res = ListNode(-1)
        tmp = res

        while h1 != None and h2 != None:
            if h1.val < h2.val:
                res.next = h1
                h1 = h1.next
                res = res.next
            else:
                res.next = h2
                h2 = h2.next
                res = res.next 

        while h1 != None:
            res.next = h1
            h1 = h1.next
            res = res.next

        while h2 != None:
            res.next = h2
            h2 = h2.next
            res = res.next 
        
        return tmp.next
```

這裡 `res` 是**一路往前移動的游標**，`tmp` 是那顆固定不動的 dummy head。（名字容易看反 —— 大多數人會把 dummy 叫 `dummy`、游標叫 `cur`，寫的時候留意一下自己的命名，面試時解釋起來比較順。）

**後面那兩個 `while` 可以縮成一行。** 跳出主迴圈時最多只有一邊還有剩，而且它已經排序好了，鏈結串列不需要逐顆搬 —— 直接把整條接上去：

```python
        res.next = h1 if h1 else h2
```

或者更 Python 一點：`res.next = h1 or h2`。這是鏈結串列比陣列漂亮的地方：陣列合併時剩下的元素得一個個複製，串列只要改一個指標。

## 補充

**`<` 還是 `<=`？** 兩邊值相同時，`h1.val < h2.val` 會走 `else` 分支先接 `h2`。答案一樣正確，但這樣**不是穩定的**（相同值時來自 list2 的排在前面）。這題不在意，不過如果面試官問「合併排序要穩定的話呢」，答案就是把條件改成 `<=`。

**合併家族**：

| 題目 | 資料結構 | 合併幾條 | 核心工具 |
|---|---|---|---|
| **21 這題** | 鏈結串列 | 2 | dummy head + 兩指針 |
| [23. Merge k Sorted Lists](/interview/coding/23-merge-k-sorted-lists) | 鏈結串列 | **k** | heap 或兩兩分治 |
| [88. Merge Sorted Array](/interview/coding/88-merge-sorted-array) | **陣列**（原地） | 2 | **從後往前填** |

**這組對照最值得記的是「為什麼只有 88 要反過來」**：串列合併只改指標，寫入不破壞資料；陣列原地合併從前面寫會蓋掉還沒讀的元素。**資料結構決定了方向。**

23 則是把這題當子程序用 —— 兩兩分治那個解法裡的 `mergeTwoLists` 就是本題。[148. Sort List](/interview/coding/148-sort-list) 也一樣（合併排序的完整版，這題是它的合併步驟）。

## 複雜度

- 時間 $O(m + n)$ — 兩條串列的每個節點都只被走過一次
- 空間 $O(1)$ — 只有幾個指標；接的是原本的節點，沒有建新節點（dummy head 那一顆是常數）

其中 `m`、`n` 是兩條串列的長度。