給定一個單向鏈結串列
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
TIP
核心思路：找到中點、反轉後半段、交錯合併前後兩段 — 三步走策略。
- 觀察重排模式：第一個接最後一個、第二個接倒數第二個…
- 這等價於：前半段 + 反轉後的後半段，交替合併
- 三個子問題都是鏈結串列的經典操作
Approaches
1. Using Array (Extra Space) — O(n) / O(n)
- Idea: 將所有節點存入陣列，利用雙指針從兩端向中間交替重建串列
- Time:
O(n)- 遍歷兩次 - Space:
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) — O(n) / O(1)
- Idea: (1) 快慢指針找中點 (2) 反轉後半段 (3) 交錯合併前後兩段
- Time:
O(n)- 三步各 O(n) - Space:
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
}
}
}WARNING
找中點時注意奇偶長度的差異。fast?.next?.next != null 確保 slow 停在前半段的最後一個節點，這樣 slow.next 才是後半段的起點。
🔑 Takeaways
- Pattern: 「找中點 + 反轉 + 合併」三步走是鏈結串列重排的經典組合技
- Key trick: 快慢指針找中點、原地反轉、交錯合併，三個基礎操作務必熟練