Intersection of Two Linked Lists #160

題意

• 給兩個單向鏈表，判斷它們是否在某個節點相交，若相交則回傳相交節點，否則回傳 null。

thoughts

方法一：

• 計算兩個鏈表長度，讓長的先走差值步數，再一起走，直到相遇或走到結尾。
  方法二（經典）：

• 用兩個指針 a、b，分別從兩個鏈表頭出發。

• 當走到尾巴時轉向到另一個鏈表頭。

• 最多 2 次遍歷後，若有交點則必相遇，否則同時到 null。

• 時間：O(m + n)

• 空間：O(1)

Kotlin

fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
    var a = headA
    var b = headB
    while (a != b) {
        a = if (a == null) headB else a.next
        b = if (b == null) headA else b.next
    }
    return a
}

Follow-up

• 如果鏈表是循環結構，該如何處理？
• 如果鏈表非常長，能否在 streaming 或外部儲存模型下解？