萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

單向鏈表反轉:遞迴與非遞迴兩種演算法完整圖解與代碼實作

問題定義

給定單向鏈表 a → b → c → d,將其原地反轉為 d → c → b → a,並傳回新頭節點。

節點結構:

class Node {
    char value;
    Node next;
}

演算法一:非遞迴(迭代三指針法)

核心邏輯

  1. 維護三指標:previousNode(已反轉部分尾部)、current(待處理節點)、nextNode(暫存原後繼)。
  2. 每輪將 current.next 指向 previousNode,再整體右移三指標。
  3. 迴圈結束時 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;  // 新頭節點
}

圖解過程(以 a→b→c 為例)

初始: 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

複雜度

  • 時間:O(N) — 單趟遍歷。
  • 空間:O(1) — 僅常數額外空間。

演算法二:遞迴

核心邏輯

  1. 遞迴走到尾節點(current.next == null),直接回傳該節點作為新頭。
  2. 回溯階段:將 current.next.next = current(把下一節點指回自己),再 current.next = null 斷開舊連結。
  3. 層層返回新頭節點。

完整代碼

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(N)。
  • 空間:O(N) — 遞迴呼叫堆疊深度等於節點數,極長鏈表可能堆疊溢位。

兩法比較與選型指南

維度非遞迴遞迴
空間複雜度O(1)O(N)
程式碼簡潔度稍長極簡
堆疊溢位風險無長鏈表有風險
除錯容易度易(單步追蹤)難(堆疊深)
推薦場景生產環境、長鏈表教學、短鏈表、函數式風格

進階延伸

  • 部分鏈表反轉:reverseBetween(head, m, n) — 結合虛擬頭節點與計數器。
  • K 群組反轉:reverseKGroup(head, k) — 遞迴或迭代分組處理。
  • 雙向鏈表反轉:同步修正 prev 指標。

掌握兩種反轉寫法,不僅能應付面試經典題,更能深化對指標操作與遞迴思維的理解。

copyright © 萬盛學電腦網 all rights reserved