143. Reorder List

Medium

Description

給定一個單向鏈結串列 L0 -> L1 -> ... -> Ln-1 -> Ln，將其重新排列為 L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...。不可修改節點的值，只能修改節點本身。

Example:

Input: head = [1,2,3,4,5] Output: [1,5,2,4,3]

Intuition#

核心思路：找到中點、反轉後半段、交錯合併前後兩段 – 三步走策略。

觀察重排模式：第一個接最後一個、第二個接倒數第二個…
這等價於：前半段 + 反轉後的後半段，交替合併
三個子問題都是鏈結串列的經典操作

Approaches#

1: Using Array (Extra Space)#

概念: 將所有節點存入陣列，利用雙指針從兩端向中間交替重建串列
時間複雜度: O(n) - 遍歷兩次
空間複雜度: O(n) - 需要陣列儲存所有節點

class Solution {
    fun reorderList(head: ListNode?): Unit {
        if (head?.next == null) return

        val nodes = mutableListOf<ListNode>()
        var curr = head
        while (curr != null) {
            nodes.add(curr)
            curr = curr.next
        }

        var left = 0
        var right = nodes.size - 1
        while (left < right) {
            nodes[left].next = nodes[right]
            left++
            if (left == right) break
            nodes[right].next = nodes[left]
            right--
        }
        nodes[left].next = null
    }
}

⭐2: Find Middle + Reverse + Merge (In-Place)#

概念: (1) 快慢指針找中點 (2) 反轉後半段 (3) 交錯合併前後兩段
時間複雜度: O(n) - 三步各 O(n)
空間複雜度: O(1) - 原地操作

class Solution {
    fun reorderList(head: ListNode?): Unit {
        if (head?.next == null) return

        // Step 1: 快慢指針找中點
        var slow = head
        var fast = head
        while (fast?.next?.next != null) {
            slow = slow!!.next
            fast = fast.next!!.next
        }

        // Step 2: 反轉後半段
        var prev: ListNode? = null
        var curr = slow!!.next
        slow.next = null
        while (curr != null) {
            val next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        }

        // Step 3: 交錯合併
        var first = head
        var second = prev
        while (second != null) {
            val tmp1 = first!!.next
            val tmp2 = second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2
        }
    }
}

找中點時注意奇偶長度的差異。fast?.next?.next != null 確保 slow 停在前半段的最後一個節點，這樣 slow.next 才是後半段的起點。

🔑 Takeaways#

Pattern: 「找中點 + 反轉 + 合併」三步走是鏈結串列重排的經典組合技
關鍵技巧: 快慢指針找中點、原地反轉、交錯合併，三個基礎操作務必熟練