題目說明

160. Intersection of Two Linked Lists
     給定兩個單向鏈結串列，判斷它們是否相交，並找出相交的節點。
     如果沒有相交，回傳 null。
     ⚠️ 題目保證兩個鏈結串列的結構不會有 cycle。

範例

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

Output: c1

程式碼

Python 解法

class ListNode:
def init(self, x):
self.val = x
self.next = None
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
p1, p2 = headA,headB
while p1 != p2:
p1 = p1.next if p1 else headB
p2 = p2.next if p2 else headA
return p1

Java 解法

public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
p1 = (p1 == null) ? headB : p1.next;
p2 = (p2 == null) ? headA : p2.next;
}
return p1;
}
}

複雜度分析

• 時間複雜度：O(m + n)，m 與 n 分別是兩個鏈結串列的長度。
  兩個指針最多各走兩遍長度就會相遇或結束。
• 空間複雜度：O(1)，只用兩個指針。