Intersection of Two Linked Lists (LeetCode 160)

The problem

You get the heads of two singly linked lists, a and b. At some node they may merge and share the same tail from then on. Return that first shared node, or None if they never meet. “Shared” means the same node object, not just an equal value.

List A:       4 -> 1 \
                      8 -> 4 -> 5
List B:  5 -> 6 -> 1 /

Output: the node with value 8

Both lists end in the same three nodes 8 -> 4 -> 5. The first of those is the intersection. The two 1s are different nodes, so they don’t count.

How to think about it

Start with brute force. For each node in A, scan all of B looking for the same object. That is O(n·m). A better first answer: put every node of A in a set, then walk B and return the first node already in the set. That is O(n + m) time but O(n) space.

Why two simple pointers don’t work. If both lists had the same length before the merge, you could walk them in lockstep and they would arrive at the intersection together. The problem is the length difference: A has 2 nodes before the merge, B has 3, so lockstep pointers are always one node apart.

The key insight: walk A then B, and B then A. Pointer pa walks A, and when it falls off the end it jumps to B’s head. Pointer pb does the opposite. Now each pointer travels (A's private part) + (shared part) + (B's private part) before reaching the intersection a second time, in a different order. Same distance, so they arrive together. If there is no intersection, both travel lenA + lenB and reach None at the same moment, which also ends the loop.

Which pattern is this? Two pointers on linked lists. The tell is “two lists of unknown, different lengths that need to line up”.

Approach

1. Set pa = a and pb = b.
2. While pa and pb are not the same node:
   • move pa forward, or to b if it is None;
   • move pb forward, or to a if it is None.
3. Return pa. It is either the intersection node or None.

Solution

def intersection_node(a, b):
    pa, pb = a, b
    while pa is not pb:                    # compare node identity, not value
        pa = pa.next if pa else b          # end of A -> jump to B
        pb = pb.next if pb else a          # end of B -> jump to A
    return pa
# lists [4,1]->[8,4,5] and [5,6,1]->[8,4,5] share tail 8 -> node with val 8

Dry run

On the example (A has 5 nodes, B has 6). Values show the node each pointer is on after the step; None is the end of a list:

After nine steps both pointers sit on the shared 8. On two separate lists 2 6 4 and 1 5, both pointers reach None together after six steps and the function returns None.

Complexity

• Time: O(n + m). Each pointer walks at most both lists once, plus one None step each.
• Space: O(1). Two pointers.

Edge cases and pitfalls

• No intersection: the loop still terminates, because both pointers hit None on the same step. That is why the None step is part of the walk.
• One list empty: the pointer on the empty list jumps straight to the other head, and the function returns None after walking it.
• Comparing values instead of nodes gives wrong answers. Step 8 above has two different nodes with value 1.
• Jumping on pa.next is None instead of pa is None skips the None step. With no intersection the pointers then cycle forever.
• Lists merge at the head (A and B are the same list): pa is pb from the start and it returns a.

Related problems

• Linked List Cycle II (LeetCode 142): another “make two pointers travel equal distances” argument.
• Remove Nth Node From End of List (LeetCode 19): two pointers with a fixed gap.
• Merge Two Sorted Lists (LeetCode 21): walking two lists side by side.