您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

劍指 Offer 面試題 5：從尾到頭打印鏈表——四種解法全解析

編輯：Java 相關知識

經典鏈表題：輸入單鏈表頭節點，從尾到頭打印節點值。本文詳細講解四種解法——棧、遞歸、ArrayList 逆序、就地反轉鏈表，對比時空複雜度、優缺點與適用場景，附完整 Java 代碼與測試用例。

題目描述

輸入：1 → 2 → 3 → 4 → null
輸出：4, 3, 2, 1,

本質是「後進先出」問題，天然適合棧或遞歸。

鏈表節點定義

static class ListNode {
    int val;
    ListNode next;
    ListNode(int v) { val = v; }
}

解法一：棧（顯式棧模擬後進先出）

public static void printWithStack(ListNode head) {
    Stack<Integer> stack = new Stack<>();
    while (head != null) {
        stack.push(head.val);
        head = head.next;
    }
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + ",");
    }
}

時間：O(n) 兩次遍歷
空間：O(n) 棧空間
優點：不修改原鏈表，邏輯直觀，無棧溢出風險。

解法二：遞歸（系統調用棧隱式實現）

public static void printRecursive(ListNode head) {
    if (head == null) {
        System.out.println("空鏈表");
        return;
    }
    if (head.next != null) printRecursive(head.next);
    System.out.print(head.val + ",");
}

時間：O(n)
空間：O(n) 調用棧
缺點：鏈表過長（> 10^4）易 StackOverflowError；不可中斷/恢復。

解法三：ArrayList 收集後逆序遍歷

public static void printWithArrayList(ListNode head) {
    if (head == null) { System.out.print("空鏈表"); return; }
    List<Integer> list = new ArrayList<>();
    while (head != null) {
        list.add(head.val);
        head = head.next;
    }
    for (int i = list.size() - 1; i >= 0; i--) {
        System.out.print(list.get(i) + ",");
    }
}

時間：O(n)
空間：O(n) ArrayList 底層陣列
優點：隨機訪問靈活，可多次遍歷，無棧溢出風險。

解法四：就地反轉鏈表（修改結構，O(1) 額外空間）

public static void printByReverse(ListNode head) {
    ListNode reversed = reverseRecursive(head);
    while (reversed != null) {
        System.out.print(reversed.val + ",");
        reversed = reversed.next;
    }
}

// 遞歸反轉
private static ListNode reverseRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

時間：O(n)
空間：O(n) 遞歸棧（可改迭代反轉達到 O(1)）
缺點：破壞原鏈表結構，若後續仍需原順序需再反轉一次或備份。

迭代版反轉（真正 O(1) 空間）

private static ListNode reverseIterative(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

四種解法綜合對比

解法	時間	額外空間	修改原表	棧溢出風險	推薦場景
棧	O(n)	O(n)	否	無	通用、面試首選
遞歸	O(n)	O(n) 棧	否	高	短鏈表、代碼簡潔優先
ArrayList	O(n)	O(n)	否	無	需多次逆序訪問
就地反轉	O(n)	O(1) 或 O(n)	是	遞歸版有	空間極受限、允許修改

完整測試主程式

public static void main(String[] args) {
    // 建構 1→2→3→4
    ListNode n1 = new ListNode(1);
    ListNode n2 = new ListNode(2);
    ListNode n3 = new ListNode(3);
    ListNode n4 = new ListNode(4);
    n1.next = n2; n2.next = n3; n3.next = n4;

    System.out.print("棧：");        printWithStack(n1);        System.out.println();
    System.out.print("遞歸：");      printRecursive(n1);      System.out.println();
    System.out.print("ArrayList："); printWithArrayList(n1); System.out.println();
    System.out.print("反轉：");      printByReverse(n1);      System.out.println();

    // 邊界測試
    printRecursive(null);       // 空鏈表
    printRecursive(new ListNode(5)); // 單節點
}