Intersection of Two Linked Lists — Two Pointer Length Trick

Problem 213 · Intersection of Two Linked Lists

Difficulty: Easy · Pattern: Two Pointers (length equalizer)

Intuition

Two pointers start at each head. When one reaches null, redirect it to the other head. They meet at the intersection (or null if none) after at most m+n steps.

Solutions

# Python
def getIntersectionNode(headA, headB):
    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

// Java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = a != null ? a.next : headB;
        b = b != null ? b.next : headA;
    }
    return a;
}

// C++
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *a = headA, *b = headB;
    while (a != b) {
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;
}

Complexity

Time: O(m+n)
Space: O(1)