Description
給定兩個單向鏈結串列的頭節點
headA和headB，找出兩個鏈結串列的交叉節點。若無交叉則回傳null。注意交叉是以節點引用判斷，不是節點值。
Example:
Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 Output: Intersected at ‘8’
Intuition#
核心思路：兩個指針分別從 A 和 B 出發，走完自己的串列後切換到對方的串列，最終會在交叉點相遇。
- 兩個串列長度可能不同，直接同步遍歷無法對齊
- 關鍵觀察：A 的長度 + B 的長度 = B 的長度 + A 的長度，所以兩指針走完兩條路後一定對齊
- 若無交叉，兩指針最後都會到 null，也會同時結束
Approaches#
1: HashSet#
- 概念: 先將 A 的所有節點存入 HashSet，再遍歷 B 找第一個存在於 Set 中的節點
- 時間複雜度:
O(m + n) - 空間複雜度:
O(m)- 儲存 A 的所有節點
class Solution {
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
val visited = HashSet<ListNode>()
var curr = headA
while (curr != null) {
visited.add(curr)
curr = curr.next
}
curr = headB
while (curr != null) {
if (curr in visited) return curr
curr = curr.next
}
return null
}
}⭐2: Two Pointers (Switch Lists)#
- 概念: 指針 A 走完 listA 後接到 listB 的頭，指針 B 走完 listB 後接到 listA 的頭，兩者會在交叉點相遇
- 時間複雜度:
O(m + n) - 空間複雜度:
O(1)
class Solution {
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
var pA = headA
var pB = headB
while (pA !== pB) {
pA = if (pA != null) pA.next else headB
pB = if (pB != null) pB.next else headA
}
return pA
}
}比較節點時必須用
!==（引用比較），不是!=（值比較）。Kotlin 中==對 nullable 型別可能呼叫 equals。
🔑 Takeaways#
- Pattern: 兩指針切換串列的技巧本質是讓兩者走相同的總路徑長度，從而自動對齊
- 關鍵技巧: 當 pA 走到 null 時切到 headB（不是 headB.next），這樣能正確處理長度差