Intersection of Two Linked Lists: The Pointer Switching Proof

If you interview at Amazon, Microsoft, Airbnb, expect some version of "Intersection of Two Linked Lists". It is rated Easy, and it falls squarely into the Fast and Slow Pointers pattern — pattern-first preparation beats grinding random problems every time. Part 11 of 11 in the Fast and Slow Pointers arc.

The Problem

Given the heads of two singly linked lists that may merge at some node and share their tail, return the node where they intersect, or None. Intersection is by identity, not value. Required: O(n + m) time, O(1) space — which eliminates the hash-set answer.

A: 4 -> 1 -> 8 -> 4 -> 5
B: 5 -> 6 -> 1 -> 8 -> 4 -> 5   (merging at the node 8)
Output: node 8

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

Two pointers of a different kind: equal speed, but each switches lists on reaching an end. Walker one covers a + c + b, walker two covers b + c + a — equal totals — so they arrive together: at the intersection, or at None simultaneously.

The Approach

Advance both pointers one step at a time; when one hits the end of its list, redirect it to the other list's head. They meet at the intersection node or both become None after at most n + m + 1 steps. No length computation, no special cases.

The equal-total-distance argument is a two-sentence proof — deliver it before the code and the rest of the interview is a formality. The alternative (compute both lengths, advance the longer by the difference) is equally valid and worth naming.

Python Solution

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def get_intersection_node(
    head_a: ListNode | None, head_b: ListNode | None
) -> ListNode | None:
    """First shared node by identity, or None. O(1) space."""
    if not head_a or not head_b:
        return None
    p, q = head_a, head_b
    while p is not q:
        p = p.next if p else head_b
        q = q.next if q else head_a
    return p

Complexity

• Time: O(n + m) — each pointer traverses each list at most once
• Space: O(1) — two pointers, no set

Interview Tips and Follow-Ups

• The loop terminates even with no intersection because both pointers become None at the same step — trace it once; interviewers ask.
• If the lists could contain cycles, this breaks — combining with cycle detection first is the composed follow-up.
• Identity vs equality again: two nodes with value 8 are not the same node. Tests that compare values can lie to you.

That wraps part 11 of the Fast and Slow Pointers arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.