LeetCode 160 相交鏈表：HashSet 與雙指針 O(1) 空間解法對比

LeetCode 160 相交鏈表：HashSet 與雙指針 O(1) 空間解法對比

給定兩個單鏈表頭節點 headA、headB，找到它們的相交起始節點。相交定義為節點引用相同 (非值相等)，即兩鏈表共享同一尾部節點序列。本文對比三種解法，重點分析雙指針 O(1) 空間巧解。

題目範例

List A: a1 → a2 → c1 → c2 → c3
List B: b1 → b2 → b3 → c1 → c2 → c3
相交節點: c1 (引用相同)

無相交: 返回 null

解法一：HashSet 記錄訪問節點 (直觀、O(n) 空間)

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> visited = new HashSet<>();
    
    // 遍歷 A，記錄所有節點引用
    ListNode curr = headA;
    while (curr != null) {
        visited.add(curr);
        curr = curr.next;
    }
    
    // 遍歷 B，首個在 Set 中的即為相交點
    curr = headB;
    while (curr != null) {
        if (visited.contains(curr)) {
            return curr; // 找到相交節點
        }
        curr = curr.next;
    }
    return null; // 無相交
}

複雜度

• 時間：O(m + n)
• 空間：O(m) 或 O(min(m,n)) (可選較短鏈表存入)

解法二：雙指針「路徑對齊」法 (O(1) 空間、天才解法)

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    
    ListNode pA = headA, pB = headB;
    
    // 關鍵：兩指針走過的總路徑長度相等 = lenA + lenB
    // 若有相交：在相交點相遇
    // 若無相交：同時到達 null 退出
    while (pA != pB) {
        pA = (pA == null) ? headB : pA.next; // 走完 A 轉走 B
        pB = (pB == null) ? headA : pB.next; // 走完 B 轉走 A
    }
    
    return pA; // 相交節點或 null
}

核心數學證明

設：

• 鏈表 A 非公共部分長度 a
• 鏈表 B 非公共部分長度 b
• 公共部分長度 c

指針 pA 走過路徑：a + c + b
指針 pB 走過路徑：b + c + a

總長度相等，故若有相交 (c>0)，必在相交點相遇；若無相交 (c=0)，同時走完 a+b 到達 null。

視覺化演示

A: a1 → a2 → c1 → c2 → c3 → null
                      ↑
B: b1 → b2 → b3 ──────┘

pA 路徑: a1 a2 c1 c2 c3  b1 b2 b3 c1 ← 相遇
pB 路徑: b1 b2 b3 c1 c2 c3  a1 a2 c1 ← 相遇
              ↑                    ↑
           切換到 headB         切換到 headA

解法三：先測長度再對齊 (O(1) 空間、兩遍掃描)

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);
    
    ListNode pA = headA, pB = headB;
    
    // 長鏈表先走差值步
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) pA = pA.next;
    } else {
        for (int i = 0; i < lenB - lenA; i++) pB = pB.next;
    }
    
    // 同步前進
    while (pA != pB) {
        pA = pA.next;
        pB = pB.next;
    }
    return pA;
}

private int getLength(ListNode head) {
    int len = 0;
    while (head != null) { len++; head = head.next; }
    return len;
}

複雜度總結

關鍵測試用例

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

進階變體：環形鏈表相交檢測

若鏈表可能有環，先用快慢指針檢測環並找入口，再判斷相交邏輯會複雜得多。本題假設無環。

面試加分點

1. 主動說明三種解法並對比
2. 能現場推導雙指針路徑長度相等證明
3. 指出 pA != pB 比較的是引用地址，非 val
4. 討論有環情況下的處理策略
5. 代碼處理邊界：空指針、單節點、無相交

總結

LeetCode 160 是鏈表雙指針技巧的經典展示：

• HashSet 適合快速實現、空間不敏感場景
• 雙指針路徑對齊 是空間最優解，體現「以時間換空間」的反直覺智慧
• 長度對齊 工程上更易維護、除錯

掌握雙指針「走過相同總路徑」的核心思想，能舉一反三解決：鏈表中點、倒數第 K 個、環檢測、環入口等全家族問題。

1. 上一篇文章： Java IO 序列化機制與裝飾器/適配器模式深度解析
2. 下一篇文章： JDBC 最佳實踐：為什麼必須用 PreparedStatement 替代 Statement

Java 綜合教學

Struts2 動態方法調用（DMI）：透過表單 Action 屬性切換業務邏輯

Struts2 動態方法調用（DMI）詳解 在 Struts

JVM 記憶體結構與 GC 核心原理：運行時資料區、垃圾收集算法、Minor/Full GC 觸發條件

JVM 記憶體結構與 GC 核心原理完整總結 一、JVM

Java JDBC 連接 MySQL 底層實現全解析：驅動註冊、連接獲取、CRUD 封裝與工具類設計

JDBC 連接 MySQL 底層實現全解析 雖然生產多用連接

SSH 框架整合實戰：Struts2 + Spring + Hibernate 完整配置指南

專案背景與依賴規劃 SSH 指 Struts2（表現層）+