Skip to main content

160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists

Python​

Remember A nodes in hash table​

Time: O(a+b)

Space: O(a)

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        cur_a = headA
        a_nodes = set()
        while cur_a:
            a_nodes.add(cur_a)
            cur_a = cur_a.next

        cur_b = headB
        while cur_b:
            if cur_b in a_nodes:
                return cur_b
            cur_b = cur_b.next

        return None

Two Pointer​

Floyd's Tortoise and Hare Algorithm的變形

制在兩個Linked List中產生loop，將A尾接到B頭；B尾接到A頭

  • 若A跟B不一樣長，用龜兔賽跑算法找到連結點
  • 若A跟B一樣長，會return在第一次重疊點
  • 若A跟B沒有連結，會重疊在None，也符合題意

Time: O(a+b)

Space: O(1)

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        cur_a, cur_b = headA, headB
        while cur_a != cur_b:
            cur_a = cur_a.next if cur_a else headB
            cur_b = cur_b.next if cur_b else headA
        return cur_a