Reverse Linked List (Linked List), 206

thoughts

• 給定一個單向鏈結串列，請反轉它，並回傳新的頭節點。

Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 5 -> 4 -> 3 -> 2 -> 1 -> null

方法 1：迭代法 (Iterative) 最常見
利用三指針（prev、curr、next）逐步反轉指向。
步驟：

1. 初始化 prev = null，curr = head。
2. 每次迭代：

• 暫存下一個節點：next = curr.next
• 反轉指針：curr.next = prev
• 前進指標：prev = curr，curr = next

3. 當 curr == null 時，prev 就是新頭節點。

• 時間複雜度：O(n)
• 空間複雜度：O(1)

方法 2：遞迴法 (Recursive)
用遞迴自然地把鏈表翻轉，最後一層返回新頭。
thoughts:

• base case：如果 head == null 或 head.next == null，直接回傳 head。

• 遞迴反轉剩下的鏈表，設新頭為 newHead = reverse(head.next)。

• 修改指針：head.next.next = head，並設 head.next = null。

• 回傳 newHead。

• 時間複雜度：O(n)

• 空間複雜度：O(n)（因為遞迴呼叫堆疊）

方法 3：用 Stack（不推薦面試）

• 遍歷鏈表，把所有節點 push 進 stack。

• 再 pop 出來重建鏈表。

• 時間複雜度：O(n)

• 空間複雜度：O(n)

（一般面試不會用 stack，因為效率不佳）

Kotlin

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        var prev: ListNode? = null
        var curr = head
        while (curr != null) {
            val nextNode = curr.next
            curr.next = prev
            prev = curr
            curr = nextNode
        }
        return prev
    }
}

Follow-up

• 如何用遞迴解法？
• 反轉部分區間 (m 到 n 節點) 要怎麼做？
• 如果鏈結串列長度非常大，遞迴解法會有什麼風險？（Stack Overflow）
• 能不能就地反轉？ => 可以，用迭代法即可，空間 O(1)。
• 能否只反轉前 k 個節點？ => 以在迭代過程中加計數器。
• 如何反轉從位置 m 到 n 的子鏈表？（LeetCode 92）
  • 在迭代過程中找到 m 和 n 的邊界，斷開並反轉，再接回去。
• 如何處理雙向鏈表的反轉？
  • 需要交換每個節點的 prev 和 next 指標。