給定一個單向鏈結串列的頭節點
head，將整個鏈結串列反轉後回傳新的頭節點。
Example:
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Intuition
TIP
核心思路：逐一改變每個節點的 next 指針方向，讓它指向前一個節點。
- 鏈結串列反轉的本質就是把每條邊的方向反過來
- 迭代法：用三個指針 (prev, curr, next) 逐步翻轉
- 遞迴法：先遞迴到尾端，回溯時反轉指針
Approaches
1. Recursive — O(n) / O(n)
- Idea: 遞迴到鏈結串列的尾端，回溯時將每個節點的 next 節點的 next 指回自己，最後將自己的 next 設為 null
- Time:
O(n)- 每個節點訪問一次 - Space:
O(n)- 遞迴呼叫堆疊深度為 n
class Solution {
fun reverseList(head: ListNode?): ListNode? {
if (head?.next == null) return head
val newHead = reverseList(head.next)
head.next!!.next = head
head.next = null
return newHead
}
}⭐ 2. Iterative (Three Pointers) — O(n) / O(1)
- Idea: 使用 prev、curr、next 三個指針，逐步將每個節點的 next 指向前一個節點
- Time:
O(n)- 只需遍歷一次 - Space:
O(1)- 只用三個指針變數
class Solution {
fun reverseList(head: ListNode?): ListNode? {
var prev: ListNode? = null
var curr = head
while (curr != null) {
val next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}
}WARNING
遞迴解法在鏈結串列很長時可能導致 Stack Overflow。面試時通常偏好迭代解法。
🔑 Takeaways
- Pattern: 鏈結串列反轉是最基礎的鏈結串列操作，是許多進階題的子問題（如 k-Group Reverse、Reorder List）
- Key trick: 三指針迭代法是 O(1) 空間反轉鏈結串列的標準做法，務必熟練