---
title: "143. Reorder List"
url: "https://laigary.com/interview/coding/143-reorder-list"
type: "note"
section: "coding"
date: "2025-12-24"
updated: "2026-07-26"
tags: ["Linked List", "Two Pointers"]
---

# 143. Reorder List

[143\. Reorder List](https://leetcode.com/problems/reorder-list/)

把 `L0 → L1 → … → Ln-1 → Ln` 重排成 `L0 → Ln → L1 → Ln-1 → …`，要原地做。

## 思路

想要的結果是「頭一個、尾一個、頭二個、尾二個…」交錯排列。如果是**陣列**，這題很簡單：左右各一個索引往中間收就好。但這是**單向串列**，拿不到「倒數第 k 個」—— 每次都要從頭走一遍找尾巴，那是 $O(n^2)$。

關鍵轉念是：**與其反覆去找尾巴，不如把後半段整條反轉過來。**

反轉之後，「從尾巴往前走」就變成「從新的頭往後走」，兩條串列各自從頭往後走再交錯合併，就是 $O(n)$。

於是整題拆成三個都會的子問題：

1. **找中點** —— 快慢指針，見 [876. Middle of the Linked List](/interview/coding/876-middle-of-the-linked-list)
2. **反轉後半** —— 見 [206. Reverse Linked List](/interview/coding/206-reverse-linked-list)
3. **交錯合併** —— 兩條串列輪流接

這種「拆成三個已知子問題」的結構是這題被當作經典題的原因。面試時先講出這三步，再逐個實作，比直接埋頭寫穩得多。

**切斷的那一刀很重要**：找到中點後要把前半段的尾巴指向 `None`，否則反轉後前後兩段會互相指、形成環，交錯合併時會無限迴圈。

## 解題方向

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # slow point to the middle point of the linked list

        def reverse(node):
            if not node or not node.next:
                return node
            last = reverse(node.next)
            node.next.next = node
            node.next = None
            return last

        r = reverse(slow.next)
        slow.next = None

        tmp = head
        while r:
            tmp_next = tmp.next
            r_next = r.next
            
            tmp.next = r        
            r.next = tmp_next
            
            tmp = tmp_next
            r = r_next
        
        return head
```

**為什麼反轉的是 `slow.next` 而不是 `slow`？** 因為 `slow` 停在「後面那個中點」（見 876 的說明），它要留在前半段當結尾。反轉從它的下一顆開始，前半段就會比後半段多一顆或一樣多 —— 這正好是交錯合併需要的形狀（先放前半的元素，所以前半不能比後半短）。

**交錯合併那段一定要先把兩邊的 `next` 存起來**（`tmp_next` / `r_next`），因為 `tmp.next = r` 這行會立刻蓋掉 `tmp` 原本的下一顆。先存後改，是所有改指標題目的通則。

迴圈條件是 `while r`（後半段走完就停），因為前半段可能比後半段多一顆，那一顆的 `next` 已經在上一輪被正確接好了。

## 補充

**遞迴版的 `reverse` 深度等於後半段的長度。** 在 Python 預設的 `recursionlimit = 1000` 下，本機跑 n = 5000 就會 `RecursionError`（判題環境通常會調高）。

改成迭代版就沒有這個問題，而且更短：

```python
        def reverse(node):
            prev = None
            while node:
                nxt = node.next
                node.next = prev
                prev = node
                node = nxt
            return prev
```

`prev / node / nxt` 三個指針往前滾，是反轉串列的標準寫法，而且沒有遞迴深度的顧慮。

**函式簽名說 `-> None`，但這份程式碼回傳了 `head`。** 題目要求原地修改、不回傳，多回傳一個值不會判錯，不過照著簽名寫比較嚴謹。

**同一組工具的其他題**：[206. Reverse Linked List](/interview/coding/206-reverse-linked-list)、[92. Reverse Linked List II](/interview/coding/92-reverse-linked-list-ii)（只反轉中間一段）、[876. Middle of the Linked List](/interview/coding/876-middle-of-the-linked-list)、[148. Sort List](/interview/coding/148-sort-list)（也是先找中點再切開）。整理見 [Linked List 模板](/interview/coding/linked-list-template)。

## 複雜度

- 時間 $O(n)$ — 找中點 $O(n)$、反轉後半 $O(n/2)$、交錯合併 $O(n/2)$，三個線性步驟相加
- 空間 $O(1)$（迭代版反轉）或 $O(n)$（遞迴版反轉，堆疊深度等於後半段長度）

其中 `n` 是節點數。全程只改指標、沒有建新節點，所以迭代版是真正的原地重排。