# 題目
給定一個單向 Linked List，反轉該鏈表並返回反轉後的頭節點。
Example:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]# 觀念
反正就記得，反轉一條鏈表，就是把每個節點的 next 指標指向前一個節點
| 特性 | Python list ([]) |
Linked List |
|---|---|---|
| 底層結構 | 動態陣列 (連續記憶體) | 節點 (物件) + 指標 |
| 存取第 i 個元素 | O(1) | O(n) (要走訪) |
| 插入 / 刪除 | O(n) (中間要搬移) | O(1) (只改指標) |
| 記憶體配置 | 連續 | 不連續 |
| 適合情境 | 頻繁隨機存取 | 頻繁插入 / 刪除 |
| 5 | 5 → 4 → 3 → 2 → 1 → None |
5 的 next 指向 4，curr 變 None |
# Linked List
class Solution:
def reverseList(head: ListNode) -> ListNode:
prev, curr = None, head
while curr:
temp = curr.next # 先暫存下一個節點，避免斷鏈 #
curr.next = prev # 把 curr 的 next 指向 prev，完成反轉，變 None <- 1 <- ...
prev = curr # 把目前的節點 curr 指向 prev
curr = temp # curr 指向下一個節點
return prev 逐步拆解執行流程：
| Step | curr | temp = curr.next | 執行 curr.next = prev 後 |
prev = curr | curr = temp | prev 指向的鏈表 |
|---|---|---|---|---|---|---|
| 0 (初始) | 1 | - | - | None | 1 | None |
| 1 | 1 | 2 | 1 → None |
1 | 2 | 1 → None |
| 2 | 2 | 3 | 2 → 1 → None |
2 | 3 | 2 → 1 → None |
| 3 | 3 | 4 | 3 → 2 → 1 → None |
3 | 4 | 3 → 2 → 1 → None |
| 4 | 4 | 5 | 4 → 3 → 2 → 1 → None |
4 | 5 | 4 → 3 → 2 → 1 → None |
| 5 | 5 | None | 5 → 4 → 3 → 2 → 1 → None |
5 | None | 5 → 4 → 3 → 2 → 1 → None |
- Time Complexity:
O(n) - Space Complexity:
O(1)
# 參考
初次學 Linked List 可能會有點抽象，這邊分享當初看到一個非常淺顯易懂的 yt 教學
