Intersection of Two Linked Lists

Intuition

Let the two lists have lengths a and b with a shared suffix of length c. If a pointer that finishes list A continues from the head of list B, and vice versa, then each pointer travels exactly a + b nodes before running out. Because both pointers cover the same combined distance, they arrive at the intersection node at the very same step. If the lists never intersect, both pointers reach null at the same time and the comparison ends the loop with a null answer. This elegantly cancels out the length difference without measuring either list explicitly.

Algorithm walkthrough

1. 1Set pointer a to headA and pointer b to headB.
2. 2Loop while a and b are not the same node reference.
3. 3Advance a to a.next, but when a is null redirect it to headB instead.
4. 4Advance b to b.next, but when b is null redirect it to headA instead.
5. 5After at most len(A) + len(B) steps the pointers are equal; return that node (the intersection or null).

Implementation

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a, b = headA, headB
        while a is not b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a