Java 實現單鏈表反轉：從 A→B→C 到 C→B→A 的完整代碼解析

問題描述

給定單鏈表節點定義：

class Node {
    int value;
    Node next;
}

需要實現 Node change(Node head) 方法，將鏈表原地反轉。例如 A→B→C 變為 C→B→A，並返回新頭節點 C。

核心思路：迭代法（三指針法）

使用三個指針：prev（前驅）、curr（當前）、next（後繼）。遍歷過程中不斷反轉 next 指針方向。

完整可運行代碼

public class LinkedListReverse {

    static class Node {
        int value;
        Node next;
        Node(int value) { this.value = value; }
    }

    // 反轉鏈表核心方法
    public static Node change(Node head) {
        Node prev = null;
        Node curr = head;
        while (curr != null) {
            Node next = curr.next; // 暫存後繼
            curr.next = prev;      // 反轉指針
            prev = curr;           // 前驅前移
            curr = next;           // 當前前移
        }
        return prev; // 新頭節點
    }

    // 輔助：構建鏈表
    public static Node buildList(int... values) {
        if (values.length == 0) return null;
        Node head = new Node(values[0]);
        Node cur = head;
        for (int i = 1; i < values.length; i++) {
            cur.next = new Node(values[i]);
            cur = cur.next;
        }
        return head;
    }

    // 輔助：打印鏈表
    public static void print(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.value).append(" → ");
            head = head.next;
        }
        sb.append("null");
        System.out.println(sb);
    }

    public static void main(String[] args) {
        Node head = buildList(1, 2, 3, 4, 5);
        System.out.print("原鏈表: ");
        print(head);
        Node newHead = change(head);
        System.out.print("反轉後: ");
        print(newHead);
    }
}

關鍵點解析

• 邊界處理：空鏈表、單節點鏈表均正確返回。
• 空間複雜度 O(1)：僅使用常數額外空間。
• 時間複雜度 O(n)：單次遍歷。
• 原地修改：不創建新節點，直接操作現有節點的 next 指針。

遞歸版本（補充）

public static Node reverseRecursive(Node head) {
    if (head == null || head.next == null) return head;
    Node newHead = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

遞歸版本代碼簡潔，但棧深度為 O(n)，極長鏈表可能棧溢出，生產環境推薦迭代版。