一、什麼是單鏈表？¶
在開始之前，我們需要先了解一下單鏈表的基本結構。單鏈表是一種常見的數據結構，由多個節點（Node）組成。每個節點包含兩部分：數據域（存儲數據）和指針域（存儲指向下一個節點的地址，在 Python 中通常用 next 表示）。鏈表的第一個節點稱爲“頭節點”，最後一個節點的指針域通常指向 None（表示鏈表結束）。
舉個例子，一個簡單的單鏈表可以表示爲：1 -> 2 -> 3 -> None，其中 1 是頭節點，每個箭頭表示 next 指針的指向。
二、爲什麼要反轉鏈表？¶
反轉鏈表是一個常見的操作，比如：
- 需要逆序輸出鏈表中的數據（例如打印鏈表時從尾到頭）；
- 解決某些算法問題（如判斷迴文鏈表、兩數相加時處理低位在前等）；
- 優化鏈表操作（如反轉後便於某些重複操作）。
三、迭代法反轉單鏈表（推薦初學者入門）¶
核心思路¶
迭代法的核心是遍歷鏈表，逐個反轉節點的指針方向。我們需要維護三個指針：prev（前一個節點）、current（當前節點）和 next（下一個節點），通過循環移動這三個指針，逐步將每個節點的 next 指針從指向下一個節點改爲指向前一個節點。
步驟詳解¶
- 初始化指針：
prev初始化爲None（反轉後鏈表的末尾），current初始化爲頭節點head。 - 遍歷鏈表：當
current不爲None時，執行以下操作：
- 保存current.next（即下一個節點）到next變量中（防止後續修改指針後丟失後續節點）；
- 將current.next指向prev（反轉當前節點的指針）；
- 將prev移動到current（prev成爲新的“前一個節點”）；
- 將current移動到next（current成爲新的“當前節點”）； - 終止條件：當
current爲None時，prev就是反轉後鏈表的頭節點。
舉個例子（1->2->3->None）¶
我們以鏈表 1 -> 2 -> 3 -> None 爲例，一步步演示反轉過程：
- 初始狀態：
prev = None，current = 1，next = ? - 第一步：保存
next = current.next = 2；current.next = prev = None（此時鏈表變爲1 -> None）；prev = current = 1；current = next = 2。 - 第二步：保存
next = current.next = 3；current.next = prev = 1（此時鏈表變爲2 -> 1 -> None）；prev = current = 2；current = next = 3。 - 第三步：保存
next = current.next = None；current.next = prev = 2（此時鏈表變爲3 -> 2 -> 1 -> None）；prev = current = 3；current = next = None。 - 終止：
current爲None，反轉完成，新頭節點是prev = 3。
代碼實現（Python 示例）¶
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_iterative(head):
prev = None
current = head
while current is not None:
next_node = current.next # 保存下一個節點
current.next = prev # 反轉當前節點的指針
prev = current # prev 後移
current = next_node # current 後移
return prev # prev 此時是新的頭節點
四、遞歸法反轉單鏈表（理解遞歸思想）¶
遞歸法的核心是先反轉當前節點之後的鏈表，再將當前節點接到反轉後的鏈表末尾。遞歸的關鍵是理解“將問題分解爲更小的子問題”，並明確遞歸的終止條件和遞歸步驟。
核心思路¶
- 終止條件：如果鏈表爲空（
head is None）或只有一個節點（head.next is None），直接返回原鏈表頭節點（無需反轉）。 - 遞歸步驟：
- 遞歸調用reverse(head.next)，得到反轉後的子鏈表頭節點new_head；
- 將當前節點head的next指針（原本指向子鏈表頭節點）改爲指向head的前一個節點（即反轉後的子鏈表末尾）；
- 將當前節點head的next設爲None（使其成爲反轉後的尾節點）；
- 返回反轉後的子鏈表頭節點new_head。
舉個例子（1->2->3->None）¶
以鏈表 1 -> 2 -> 3 -> None 爲例，遞歸過程如下：
- 初始調用：
reverse(1) - 遞歸調用
reverse(2)，得到子鏈表反轉後的頭節點new_head = 3（此時子鏈表爲3 -> 2 -> None）。 - 處理當前節點
1：原head.next是2，現在需要讓2.next = 1（將1接到子鏈表末尾）；1.next = None（1成爲尾節點）。 - 返回
new_head = 3，最終反轉後的鏈表爲3 -> 2 -> 1 -> None。
代碼實現（Python 示例）¶
def reverse_recursive(head):
# 終止條件：空鏈表或只有一個節點
if head is None or head.next is None:
return head
# 遞歸反轉後面的子鏈表
new_head = reverse_recursive(head.next)
# 將當前節點接到反轉後的子鏈表末尾
head.next.next = head
# 當前節點變爲尾節點，next 設爲 None
head.next = None
return new_head # 返回反轉後的頭節點
五、總結¶
兩種方法對比¶
| 方法 | 時間複雜度 | 空間複雜度 | 特點 |
|---|---|---|---|
| 迭代法 | O(n) | O(1) | 直觀易懂，無棧溢出風險 |
| 遞歸法 | O(n) | O(n) | 代碼簡潔，但依賴遞歸棧 |
關鍵注意點¶
- 迭代法：必須注意指針移動的順序（先保存
next，再反轉指針，再移動prev和current）。 - 遞歸法：需明確終止條件（空鏈表或單節點鏈表直接返回），並理解“子問題反轉後如何連接當前節點”。
通過這兩種方法，我們掌握了單鏈表反轉的核心思想。迭代法適合初學者直接理解指針操作，遞歸法則能幫助理解遞歸思想在鏈表問題中的應用。多動手畫圖模擬指針移動過程，就能輕鬆掌握鏈表反轉的精髓！