Java 鏈表面試題全解析：從基礎操作到環檢測與合併

前言

鏈表是面試高頻考點，考察指針操作、邊界條件處理、空間換時間思維。本文系統整理 11 道經典題目，提供雙指針、遞歸、棧、快慢指針多種解法，附完整可運行代碼。

一、基礎結構定義

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class LinkedListUtil {
    // 尾插法構建
    public static ListNode build(int... vals) {
        ListNode dummy = new ListNode(0), cur = dummy;
        for (int v : vals) cur = cur.next = new ListNode(v);
        return dummy.next;
    }
    // 打印
    public static void print(ListNode head) {
        for (ListNode p = head; p != null; p = p.next) 
            System.out.print(p.val + (p.next != null ? " -> " : "\n"));
    }
    // 創建環（用於測試）
    public static void createCycle(ListNode head, int pos) {
        if (pos < 0) return;
        ListNode cycleNode = null, tail = head;
        int idx = 0;
        while (tail.next != null) {
            if (idx == pos) cycleNode = tail;
            tail = tail.next;
            idx++;
        }
        if (idx == pos) cycleNode = tail;
        tail.next = cycleNode;
    }
}

二、11 道經典題目詳細解法

1. 單鏈表創建與遍歷

尾插法 O(n)，遍歷 O(n)。注意頭節點為空處理。

2. 求鏈表長度

public int length(ListNode head) {
    int len = 0;
    for (ListNode p = head; p != null; p = p.next) len++;
    return len;
}

3. 倒數第 K 個節點（雙指針經典）

public ListNode findKthFromEnd(ListNode head, int k) {
    if (head == null || k <= 0) return null;
    ListNode fast = head, slow = head;
    // fast 先走 k-1 步
    for (int i = 0; i < k - 1; i++) {
        if (fast.next == null) return null; // k > 長度
        fast = fast.next;
    }
    // 同步前進，fast 到達尾部時 slow 指向倒數第 k
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

4. 中間節點（快慢指針）

public ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // 偶數長度返回第 n/2+1 個
}

5. 合併兩個有序鏈表（遞歸/迭代）

// 迭代法 O(1) 空間
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; }
        else { cur.next = l2; l2 = l2.next; }
        cur = cur.next;
    }
    cur.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

// 遞歸法 簡潔但 O(n) 棧空間
public ListNode mergeRecursive(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) { l1.next = mergeRecursive(l1.next, l2); return l1; }
    else { l2.next = mergeRecursive(l1, l2.next); return l2; }
}

6. 鏈表反轉（三指針迭代/遞歸）

// 迭代法：pre 保存前驅，cur 當前，next 保存後繼
public ListNode reverseIterative(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

// 遞歸法：假設 head.next 已反轉，調整指向
public 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;
}

7. 從尾到頭打印（棧/遞歸）

// 顯式棧 可控、無棧溢出風險
public void reversePrintStack(ListNode head) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (ListNode p = head; p != null; p = p.next) stack.push(p.val);
    while (!stack.isEmpty()) System.out.println(stack.pop());
}

// 遞歸 代碼極簡但深度受限
public void reversePrintRecursive(ListNode head) {
    if (head == null) return;
    reversePrintRecursive(head.next);
    System.out.println(head.val);
}

8. 判斷鏈表有環（快慢指針 Floyd 算法）

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

9. 求環長度

public int cycleLength(ListNode head) {
    ListNode meet = findMeetNode(head);
    if (meet == null) return 0;
    int len = 1;
    for (ListNode p = meet.next; p != meet; p = p.next) len++;
    return len;
}

private ListNode findMeetNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return slow;
    }
    return null;
}

10. 找環入口節點（數學推導）

原理：相遇時，slow 走 a+b，fast 走 a+b+c+b = 2(a+b) → a = c。
即：從頭節點與相遇點同步前進，相遇處即入口。

public ListNode detectCycleEntrance(ListNode head) {
    ListNode meet = findMeetNode(head);
    if (meet == null) return null;
    ListNode p1 = head, p2 = meet;
    while (p1 != p2) { p1 = p1.next; p2 = p2.next; }
    return p1;
}

11. 兩鏈表首個公共節點（長度差對齊）

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = length(headA), lenB = length(headB);
    ListNode longList = lenA > lenB ? headA : headB;
    ListNode shortList = lenA > lenB ? headB : headA;
    int diff = Math.abs(lenA - lenB);
    while (diff-- > 0) longList = longList.next;
    while (longList != shortList) {
        longList = longList.next;
        shortList = shortList.next;
    }
    return longList; // null 表示無交點
}

三、複雜度總結表

四、避坑指南

1. 空指針防護：所有 next 操作前判斷非 null
2. 邊界條件：空鏈表、單節點、k=0、k>len、無環/無交點
3. 不修改原結構：逆序打印用棧，勿反轉鏈表
4. 遞歸深度：長鏈表遞歸易 StackOverflow，優先迭代
5. 測試用例：構建帶環/相交鏈表驗證邏輯正確性

五、總結

鏈表題目核心考察指針操作熟練度與空間換時間思維。掌握雙指針（快慢/間距）、虛擬頭節點、遞歸回溯三大核心模板，配合嚴謹的邊界測試，可應對 90% 以上面試題目。建議在 LeetCode 刷對應題目（206, 21, 141, 142, 160, 19, 876）鞏固肌肉記憶。