Intersection of Two Linked Lists

Before we start

Two lists share a suffix — a common tail. How do you find where they join? The obvious approach computes lengths, aligns the longer list, then walks both forward together. The elegant approach uses two pointers that automatically align themselves by switching lists — no length computation, no alignment step, just two pointers converging. By the end you will be able to:

• Explain why switching to the other list guarantees equal total distance.
• Write the solution in six lines from memory.
• Distinguish it from the cycle-detection approach (which also works but uses O(n) space or pointer modification).

Picture this first (no code yet)

First, the slow way (so you feel the pain)

Compute the length of both lists. Advance the pointer on the longer list by the difference. Then walk both forward until they point to the same node.

def getIntersectionNode_slow(headA, headB):
    lenA = lenB = 0
    a, b = headA, headB
    while a: lenA += 1; a = a.next
    while b: lenB += 1; b = b.next

    a, b = headA, headB
    if lenA > lenB:
        for _ in range(lenA - lenB): a = a.next
    else:
        for _ in range(lenB - lenA): b = b.next

    while a and b:
        if a is b: return a
        a = a.next; b = b.next

    return None

Three passes over the lists. Correct — but wordy. The pointer-switching approach does the same in two passes with six lines.

The turning point

The one idea to remember

The code, line by line

def getIntersectionNode(headA, headB):
    a, b = headA, headB

    while a is not b:
        a = a.next if a else headB   # if A exhausted, switch to head of B
        b = b.next if b else headA   # if B exhausted, switch to head of A

    return a   # either the intersection node, or None (both exhausted together)

Six lines (two of them just the function signature and return). Read each:

• a = a.next if a else headB — advance A; if A just ran off its end (a is None), reset to the head of B. This is the "switch" moment.
• while a is not b: — keep walking until both pointers are on the same object. If no intersection exists, both become None at the same step (after walking A_len + B_len total distance) — None is None → True → loop exits → return None.
• return a — if there is an intersection, a is b at that node; return it. If not, both are None; return None.

Watch it happen, frame by frame

List A: 4 → 1 → 8 → 4 → 5 (intersection at node 8) List B: 5 → 6 → 1 → 8 → 4 → 5

Labeling nodes:

• A-only: A4, A1
• B-only: B5, B6, B1
• Shared tail: X8, X4, X5

lenA (before X8) = 2,  lenB (before X8) = 3

a starts at A4, b starts at B5

a:  A4 → A1 → X8 → X4 → X5 → None → B5 → B6 → B1 → X8
b:  B5 → B6 → B1 → X8 → X4 → X5 → None → A4 → A1 → X8

After switching (a went through None first):
Both reach X8 at step 9 (0-indexed). a is X8, b is X8.
a is b → True → exit loop. Return X8 ✅

No intersection: List A = 2 → 6 → 4, List B = 1 → 5

a: 2 → 6 → 4 → None → 1 → 5 → None
b: 1 → 5 → None → 2 → 6 → 4 → None

Both reach None at step 5. None is None → exit. Return None ✅

Why a is not b works for the "no intersection" case

When there is no intersection, after walking lenA + lenB total steps:

• a has walked all of A (lenA steps), then all of B (lenB steps), landing on None.
• b has walked all of B (lenB steps), then all of A (lenA steps), landing on None.

None is None is True in Python — the while condition a is not b becomes False and the loop exits. return a returns None. Correct, no crash, no special case needed.

Common traps

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

Check yourself

Practice problems

Next up: Reorder List — the three-step pattern: find middle, reverse second half, merge the two halves alternately.