EasyRating 1495
160. Intersection of Two Linked Lists
linked-listhash-tabletwo-pointers
解題說明
Intersection of Two Linked Lists
題目描述：給定兩個單向鏈結串列的頭節點 headA 和 headB，找出兩個串列開始相交的節點。若不相交則回傳 null。
解題思路：最優雅的解法是雙指標法。指標 a 從 headA 出發，指標 b 從 headB 出發，各自向後走；當任一指標走到末尾時，將其重定向到另一個串列的頭部繼續走。兩個指標總共走的路程相同（lenA + lenB），若存在交點，它們必定在交點相遇；若不存在交點，兩者同時到達 null。數學上：設 A 非公共部分長 a，B 非公共部分長 b，公共部分長 c，則兩指標各走 a + c + b 步後相遇於交點或 null。
C++ 解法
複雜度分析
時間複雜度：O(m + n) — 兩個指標各最多走 m + n 步，其中 m、n 為兩個串列的長度。
空間複雜度：O(1) — 只使用兩個指標，不需要額外資料結構。
虛擬碼
1. Set a = headA, b = headB 2. While a != b: a. If a is null: a = headB, else a = a.next b. If b is null: b = headA, else b = b.next 3. Return a (either intersection node or null)
其他解法
雜湊集合法：將 A 的所有節點存入集合，遍歷 B 時若找到已在集合中的節點即為交點。時間 O(m + n)，空間 O(m)，實作直觀但佔用額外記憶體。
對齊尾端法：先分別計算兩串列長度，讓較長串列的指標先走差值步，再同步前進找交點。時間 O(m + n)，空間 O(1)，但程式碼較雙指標法冗長。
延伸思考
- 如果兩個串列可能包含環，相交的定義和解法需要如何修改？
- 雙指標法的數學原理為何能保證兩指標必在交點（或 null）相遇，而非無限循環？
- 如何找出兩個有序鏈結串列的所有公共元素（值相同，非節點相同）？