Intersection of Two Linked Lists: Two-Pointer Length Equalization

Intersection of Two Linked Lists is LeetCode problem 160. It asks you to find the node where two singly linked lists converge into one. The brute-force approach (nested loops or hash sets) works, but the optimal solution uses a two-pointer trick that eliminates the length difference between the lists without ever counting nodes explicitly.

The problem

You are given the heads of two singly linked lists, headA and headB. Return the node at which the two lists intersect. If the two lists have no intersection, return null.

The intersection is defined by reference, not by value. If a node in listA is the exact same object as a node in listB, that is the intersection point. From that node onward, both lists share the same tail.

Example: listA = [4, 1, 8, 4, 5], listB = [5, 6, 1, 8, 4, 5]. The intersection starts at the node with value 8.

Notice that listA has a prefix of length 2 and listB has a prefix of length 3 before they merge. That length mismatch is the entire challenge of this problem.

Why the length difference matters

If both lists were the same length, you could simply walk two pointers forward in lockstep and check for equality at each step. But when the lists have different lengths, the pointers are out of sync. One pointer enters the shared portion earlier than the other, so they never land on the same node at the same time.

You need a way to compensate for the difference in prefix lengths. The classic approach is to measure both lengths, compute the difference, and advance the longer list's pointer by that many steps. But there is an even more elegant technique that avoids measuring lengths entirely.

The approach: two-pointer path equalization

Here is the key insight. If pointer A walks through all of listA and then continues from the head of listB, and pointer B walks through all of listB and then continues from the head of listA, they will both travel the exact same total distance before meeting at the intersection node.

Why? Let a be the number of nodes in listA's unique prefix, b be the number of nodes in listB's unique prefix, and c be the number of shared nodes.

• Pointer A travels: a + c + b nodes (all of listA, then listB's prefix up to the intersection)
• Pointer B travels: b + c + a nodes (all of listB, then listA's prefix up to the intersection)

Both paths have length a + b + c. Since addition is commutative, the total is the same regardless of which list each pointer starts with. After traveling the same total distance, both pointers arrive at the intersection node on the same step.

If there is no intersection, both pointers reach null at the same time (after traversing a + b and b + a nodes respectively). The null equality check catches this case and you return null.

Visual walkthrough

Let's trace through listA = [4, 1, 8, 4, 5] and listB = [5, 6, 1, 8, 4, 5]. Watch pA (indigo) and pB (amber) as they traverse both lists.

After pA finishes listA, it jumps to headB. After pB finishes listB, it jumps to headA. The redirect equalizes the path lengths, and they converge at node 8 on step 9.

The solution

def getIntersectionNode(headA, headB):
    pA = headA
    pB = headB

    while pA is not pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA

    return pA

That is the entire solution. Let's break it down:

1. Initialize: pA starts at headA, pB starts at headB.
2. Loop condition: pA is not pB checks reference equality. The loop runs until both pointers point to the same node (or both are null).
3. Advance pA: If pA is not null, move it forward. If it is null (reached the end of its current list), redirect it to the head of the other list.
4. Advance pB: Same logic, redirecting to headA when it reaches the end of listB.
5. Return: When the loop exits, pA and pB are either both at the intersection node or both null.

Complexity analysis

The hash set approach also runs in O(m + n) time but costs O(m) or O(n) space. The two-pointer technique matches the time complexity while dropping space to constant. That is the version interviewers want.

The building blocks

This problem is built from one core building block.

Two-pointer path equalization

When two sequences of different lengths share a common suffix, you can equalize the traversal by having each pointer walk both sequences. After one full pass, the pointer that started on the shorter sequence redirects to the longer one, and vice versa. The total distance traveled by each pointer becomes identical, so they arrive at the shared portion at the same time.

This building block is a specialized form of the two-pointer technique. Instead of using speed differences (like Floyd's cycle detection) or narrowing from both ends (like the classic two-pointer pattern on sorted arrays), it uses path concatenation to eliminate a length offset.

The same equalization idea appears in other contexts:

• Linked List Cycle II (LeetCode 142) uses a related length-offset argument. After detecting the cycle, resetting one pointer to the head and advancing both at the same speed causes them to meet at the cycle entry. The math behind why that works involves the same "total distance" reasoning.
• Remove Nth Node From End (LeetCode 19) uses a two-pointer offset. Advancing the lead pointer n steps first creates a fixed gap, then moving both pointers together causes the trailing pointer to land at the right position. Different setup, same core idea of manufacturing a specific offset between two pointers.

Edge cases

• No intersection. Both pointers reach null after traversing a + b and b + a nodes. pA is not pB becomes null is not null, which is False. The loop exits and returns null. Correct.
• One list is empty. If headA is null, pA immediately redirects to headB, but pB walks through listB and then redirects to headA (which is null). Both end up at null. Returns null. Correct.
• Same length lists. The redirect never matters. Both pointers reach the intersection (or null) on their first pass. The algorithm still works, just finishes faster.
• Intersection at the head. If headA and headB are the same node, the loop condition pA is not pB is immediately False. Returns the head node. Correct.
• One list is entirely a prefix of the other. For example, listB starts at the second node of listA. The shared suffix is all of listB. The equalization still works because the path lengths are a + b and b + a.

From understanding to recall

This problem has a solution that fits in five lines of code, but the details are subtle. Do you check pA or pA.next for the redirect? Do you use == or is? What happens when there is no intersection? These are the kinds of details that slip under pressure.

The only reliable way to retain this is to type it from scratch, repeatedly, at spaced intervals. After a few reps, the redirect logic and the while pA is not pB loop become automatic.

Related posts

• Linked List Cycle - Floyd's tortoise and hare algorithm for cycle detection, another two-pointer technique on linked lists
• Merge Two Sorted Lists - The fundamental merge operation using two pointers on linked lists, with the dummy head technique