Intersection of Two Linked Lists — The Two Pointer Length Equalizer

Problem Statement#

Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

Note: The linked list must retain their original structure after the function returns. The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Constraints:

• The number of nodes of listA is in the range [1, 3 * 10^4]
• The number of nodes of listB is in the range [1, 3 * 10^4]
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked list
• It is guaranteed that there are no cycles anywhere in the entire linked structure

Example 1:

Input:  listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], intersectVal = 8
Output: Intersection at node with value 8
Explanation: Both lists share nodes starting at value 8.

Example 2:

Input:  listA = [2,6,4], listB = [1,5], intersectVal = 0
Output: null
Explanation: No intersection.

Why This Problem Matters#

Intersection of Two Linked Lists (LeetCode 160) is a deceptively elegant problem that Amazon, Facebook (Meta), and Microsoft use to test mathematical reasoning and pointer intuition. The naive O(n) space solution (use a hash set of visited nodes) is obvious, but the optimal O(1) space solution requires you to see a non-obvious mathematical property.

This problem appears in interviews because it filters for candidates who understand that two pointers don't have to start at the same position — they can be synchronized by the total distance they travel. That insight directly applies to problems like detecting the start of a cycle (Linked List Cycle II), where you reset a pointer to the head after the meeting point.

In real-world engineering, finding shared structure between two data chains appears in version control (finding the common ancestor between two branches), file systems (hard links point to the same inode from different directory trees), and database query plans (shared subplans between query branches). The mathematical elegance of the two-pointer approach reflects a deeper pattern: when two traversals cover the same total distance, they arrive at the same point simultaneously.

The Core Insight#

Let pointer A traverse list A then list B. Let pointer B traverse list B then list A. If the lists intersect at node X, both pointers have traveled the same total distance when they reach X:

• Pointer A: len(A before intersection) + len(intersection segment) + len(B before intersection)
• Pointer B: len(B before intersection) + len(intersection segment) + len(A before intersection)

Both distances are equal. So they arrive at X at the same step. If there is no intersection, both pointers travel len(A) + len(B) steps and both hit None simultaneously — they're equal (both None), and the loop exits returning None.

The magic: no explicit length computation, no hash set, just two pointers that trade paths.

Visual Dry Run#

listA: 4 -> 1 -> 8 -> 4 -> 5 (length 5, shared tail starts at 8)

listB: 5 -> 6 -> 1 -> 8 -> 4 -> 5 (length 6, shared tail starts at 8)

Pointer A travels: 4, 1, 8, 4, 5, None→headB, 5, 6, 1, [8]

Pointer B travels: 5, 6, 1, 8, 4, 5, None→headA, 4, 1, [8]

Both reach the intersection node (value 8) at step 9. Return it.

No intersection example: [2, 6, 4] and [1, 5]

A travels: 2, 6, 4, None→headB, 1, 5, None (7 steps)

B travels: 1, 5, None→headA, 2, 6, 4, None (7 steps)

At step 7, both are None — None == None is true — loop exits, return None.

Solution (Optimal)#

Python#

def getIntersectionNode(headA, headB):
    a, b = headA, headB
    while a is not b:
        # When a reaches end of list A, redirect to headB
        a = a.next if a else headB
        # When b reaches end of list B, redirect to headA
        b = b.next if b else headA
    return a  # either the intersection node, or None

Time complexity: O(m + n) — both pointers traverse at most m + n nodes.

Space complexity: O(1) — only two pointer variables.

JavaScript#

var getIntersectionNode = function(headA, headB) {
    let a = headA, b = headB;
    while (a !== b) {
        a = a !== null ? a.next : headB;
        b = b !== null ? b.next : headA;
    }
    return a;  // intersection node or null
};

Complexity:

Hash set alternative (O(n) space):

def getIntersectionNode(headA, headB):
    seen = set()
    while headA:
        seen.add(id(headA))
        headA = headA.next
    while headB:
        if id(headB) in seen:
            return headB
        headB = headB.next
    return None

Common Mistakes#

1. Comparing node values instead of node references. Two different nodes can have the same value. The intersection is about the same physical node (same memory address), not matching values. Use is in Python, === in JavaScript — reference equality, not value equality.

2. Redirecting when the pointer is at the last node, not None. The redirect should happen when the pointer IS None (end of list), not when the pointer is at the last node. Redirecting at the last node skips it and misaligns the traversal.

3. Infinite loop if both lists are non-intersecting and the redirect logic is wrong. If you redirect a to headB when a is not None (wrong condition), or if you redirect twice without checking, you'll create an infinite loop. The correct logic redirects exactly once per pointer, when it reaches None.

4. Mutating the input lists. The problem says "The linked list must retain their original structure." Do not concatenate or modify the lists. The two-pointer approach is purely read-only.

5. Starting both pointers at the same head. Both pointers start at their respective heads (headA and headB), not at the same node. Starting both at headA would give wrong results.

Interview Tips#

1. State the two approaches upfront: "I know a hash set solution in O(m+n) time, O(m) space. The elegant O(1) space solution uses the path-swap trick."

2. Prove the math verbally: "If A has length a before intersection and B has length b before intersection, pointer A travels a + c + b total, pointer B travels b + c + a total — the same distance. They meet at the intersection."

3. Handle the no-intersection case explicitly: "If there's no intersection, both pointers hit None at the same time. None == None is true, so the loop exits and we return None. It handles itself."

4. Use the phrase "reference equality" — it shows you understand pointers deeply.

5. Draw the crossing paths — literally draw two lists with a shared tail on the whiteboard and show how the pointers swap paths. This visualization always impresses interviewers.

Follow-up Questions#

Q: How does the redirect handle the case when the lists have equal length? If both lists have equal length and share an intersection, the pointers meet at the intersection on the first pass without any redirect. If they have equal length and no intersection, they both hit None simultaneously on the first pass.

Q: What if one list is much longer than the other? The redirect equalizes the effective starting position. The longer list's pointer reaches the redirect point later, but after redirecting to the shorter list's head, the net effect is as if both started from the same offset.

Q: Can you solve it by finding lengths first? Yes — compute lengths m and n, advance the pointer in the longer list by |m - n| steps, then walk both in sync until they meet or both hit None. Same O(m+n) time and O(1) space, slightly more code.

Q: What if you need to find the intersection of three linked lists? Extend to three pointers, each redirecting through all three lists. They meet at the shared node after at most len(A) + len(B) + len(C) steps.

Q: Is there a hash-free solution that doesn't use the path-swap trick? Yes — find lengths, align the longer one, then walk together. But the path-swap trick is the canonical O(1) space solution that interviewers want to see.

Key Takeaways#

• The two-pointer path-swap trick works because both pointers travel the same total distance (m + n) whether or not there is an intersection.
• Redirect each pointer to the other list's head when it reaches None — exactly once per pointer.
• Use reference equality (is in Python, === in JavaScript) — not value equality.
• If there is no intersection, both pointers become None simultaneously, and the loop exits naturally.
• The hash set approach is O(n) space — always mention it first, then offer the O(1) space optimization.
• This pattern of "trade paths to equalize distance" recurs in Linked List Cycle II's second phase.