給定單向鏈表 a → b → c → d,將其原地反轉為 d → c → b → a,並傳回新頭節點。
節點結構:
class Node {
char value;
Node next;
}
previousNode(已反轉部分尾部)、current(待處理節點)、nextNode(暫存原後繼)。current.next 指向 previousNode,再整體右移三指標。previousNode 即為新頭節點。public Node ReverseIterative(Node current) {
Node previousNode = null;
Node nextNode = null;
while (current != null) {
nextNode = current.next; // 1. 暫存後繼
current.next = previousNode; // 2. 反轉指向
previousNode = current; // 3. 前移 previous
current = nextNode; // 4. 前移 current
}
return previousNode; // 新頭節點
}
初始: prev=null, curr=a, next=null 第1輪: next=b, a.next=null, prev=a, curr=b 第2輪: next=c, b.next=a, prev=b, curr=c 第3輪: next=null, c.next=b, prev=c, curr=null 結束: 回傳 c(新頭),鏈表為 c→b→a
current.next == null),直接回傳該節點作為新頭。current.next.next = current(把下一節點指回自己),再 current.next = null 斷開舊連結。public Node ReverseRecursive(Node current) {
if (current == null || current.next == null) return current; // 基礎案例
Node nextNode = current.next;
current.next = null; // 斷開,防止循環
Node newHead = ReverseRecursive(nextNode);
nextNode.next = current; // 反轉連結
return newHead;
}
呼叫堆疊:Reverse(a) → Reverse(b) → Reverse(c) → 回傳 c 回溯:c.next = b, b.next = a, a.next = null 最終:c → b → a
| 維度 | 非遞迴 | 遞迴 |
|---|---|---|
| 空間複雜度 | O(1) | O(N) |
| 程式碼簡潔度 | 稍長 | 極簡 |
| 堆疊溢位風險 | 無 | 長鏈表有風險 |
| 除錯容易度 | 易(單步追蹤) | 難(堆疊深) |
| 推薦場景 | 生產環境、長鏈表 | 教學、短鏈表、函數式風格 |
reverseBetween(head, m, n) — 結合虛擬頭節點與計數器。reverseKGroup(head, k) — 遞迴或迭代分組處理。prev 指標。掌握兩種反轉寫法,不僅能應付面試經典題,更能深化對指標操作與遞迴思維的理解。