Leetcode題解 Python：Intersection of Two Linked Lists

給兩串 ListNode，回傳 Intersection 的第一個點，如果沒有則回傳 None。

用 memo(hashset) 去紀錄 headA 所有走過的節。再換 headB 走，如果該節在 memo 裡，就是第一個交會點。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        memo = set()
        PointerA, PointerB = headA, headB
        while PointerA:
            memo.add(PointerA)
            PointerA = PointerA.next
        while PointerB:
            if PointerB in memo: return PointerB
            PointerB = PointerB.next           
        return None

有效歸有效，不過會消耗掉大量記憶體，在一個提示空間複雜度 O(1) 之下，這方法似乎不是最好的。

思考一下，如果要第一個交會，那麼兩者行走距離應該是最短的。但是這樣怎麼寫？

[左1右1]、[左1右2, 左2右1]、....。這樣的安排，太沒有效率了。

我一開始本來想用 traceback，這樣空間複雜度會超出 O(1)，就沒有把它寫完了。


看了一下前段班，共同點就是 headA跑完換到headB、headB跑完換到headA。

為什麼可以這樣做？

如果有交會，headA = A part + C part、headB = B part + C part。

兩者一起往下跑，跑完換別的跑，會變成 headA->headB = A part + C part + B part + C part、headB->headA = B part + C part + A part + C part。

A part + C part + B part =  B part + C part + A part，於是兩者將會在 C part 交會。

這是一個循環的技巧應用，如果有想到，就會快很多。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        PointerA, PointerB = headA, headB
        for _ in range(2):
            while PointerA and PointerB:
                PointerA = PointerA.next
                PointerB = PointerB.next
            if PointerA: PointerB = headA
            else: PointerA = headB
          
        while PointerA and PointerB:
            if PointerA == PointerB: return PointerA
            PointerA = PointerA.next
            PointerB = PointerB.next            
        return None