Intersection Linked Lists LeetCode 160

LeetCode 160 — Intersection of Two Linked Lists — gives you the heads of two singly linked lists and asks you to find the node at which the two lists intersect. If no intersection exists, return null. The key insight is that intersection is defined by reference, not by value: two nodes intersect if they are the exact same object in memory, meaning from the intersection point onward the lists share all subsequent nodes.

The two lists may have different lengths, which is what makes naive pointer alignment tricky. If list A has length 5 and list B has length 3, you cannot simply advance both pointers together from the start — you need to account for the length difference before comparing nodes. Several approaches handle this, but the most elegant is the two-pointer switch technique that compensates for the length difference automatically without computing lengths explicitly.

The follow-up constraint makes this problem especially interesting: solve it in O(1) space. A HashSet approach works in O(m+n) time but uses O(m) extra space. The two-pointer switch technique achieves O(m+n) time and O(1) space simultaneously, which is why it is the preferred interview answer.

Initialize pointer A at headA and pointer B at headB. Advance both one step at a time. When pointer A reaches null (end of listA), redirect it to headB. When pointer B reaches null (end of listB), redirect it to headA. Continue advancing both until they are equal. If they meet at a node, that node is the intersection. If both become null simultaneously, there is no intersection.

This works because both pointers travel the exact same total distance. Pointer A traverses listA (length a + c where c is the shared tail length) and then listB up to the intersection (length b). Pointer B traverses listB (length b + c) and then listA up to the intersection (length a). Both travel a + b + c steps total before meeting at the intersection node. The length difference is automatically compensated by the switch.

If there is no intersection (c = 0), pointer A travels a + b steps and pointer B travels b + a steps — both reach null at the same time after a + b steps, so the loop terminates correctly with both pointers equal to null. The algorithm handles both the intersection and no-intersection cases with the same logic.

Let a = the length of the non-shared portion of listA, b = the length of the non-shared portion of listB, and c = the length of the shared tail starting at the intersection node. Then lenA = a + c and lenB = b + c. Pointer A travels listA (a + c nodes) then switches to listB and walks b more nodes before reaching the intersection — total a + c + b steps. Pointer B travels listB (b + c nodes) then switches to listA and walks a more nodes before reaching the intersection — total b + c + a steps.

Both totals equal a + b + c, so both pointers arrive at the intersection node after the same number of steps. Since they advance in lockstep, they arrive simultaneously. This is the guarantee that makes the algorithm correct: the switch equalizes the total distance traveled regardless of the individual list lengths.

When c = 0 (no intersection), pointer A travels a + b steps and pointer B travels b + a steps — both equal a + b. Since there is no intersection node to meet at, both pointers reach null after a + b steps simultaneously. The equality check pA == pB catches this case because null == null is true, and the loop terminates returning null.

The HashSet approach is conceptually straightforward: traverse all of listA and add every node to a hash set. Then traverse listB and for each node check if it already exists in the set. The first node found in the set is the intersection node. If you traverse all of listB without a match, there is no intersection.

This approach runs in O(m + n) time — one pass over listA to build the set and one pass over listB to check — and O(m) extra space for the set storing all m nodes of listA. The space cost is the main drawback. For large lists with millions of nodes this could be significant.

In an interview, always mention both approaches. Start with the HashSet as the intuitive solution, acknowledge its O(m) space cost, then present the two-pointer switch as the space-optimal alternative. This demonstrates that you can both solve the problem and reason about trade-offs.

A third approach explicitly computes the lengths of both lists, calculates their difference d, then advances the pointer of the longer list by d steps before starting the simultaneous traversal. After this alignment step, both pointers are the same distance from the intersection (or from the end if no intersection). Advancing both together until they are equal then finds the intersection.

This approach is O(m + n) time and O(1) space — the same asymptotic complexity as the switch technique. However, it requires two extra passes to compute the lengths before the main alignment and search passes. The switch technique is preferred because it achieves the same result in fewer passes and without any explicit length computation.

The length difference approach is worth knowing as an intermediate stepping stone. It makes the intuition explicit — the key insight is that the pointer on the longer list needs to skip the first d = |lenA - lenB| nodes to align with the pointer on the shorter list. The switch technique encodes this skip implicitly via the list swap.

Python switch technique implementation: def getIntersectionNode(headA, headB): pA, pB = headA, headB; while pA != pB: pA = headB if pA is None else pA.next; pB = headA if pB is None else pB.next; return pA. The ternary switch on None handles the list swap cleanly. The loop terminates because both pointers travel the same total distance (lenA + lenB) and will be equal — either at the intersection node or both at None.

Java switch technique implementation: public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA = headA, pB = headB; while (pA != pB) { pA = (pA == null) ? headB : pA.next; pB = (pB == null) ? headA : pB.next; } return pA; } Time complexity O(m+n), space complexity O(1). The ternary operator mirrors the Python version exactly.

A common mistake is to check pA.val == pB.val instead of pA == pB. This is wrong because two different nodes at different positions can have the same value. Intersection is defined by reference equality — pA and pB must point to the same ListNode object in memory, not just nodes with matching values.

Linked List Cycle (LeetCode 141) and Linked List Cycle II (LeetCode 142) are the closest relatives. Both use the two-pointer technique with fast and slow pointers rather than switched-list pointers, but the underlying principle — exploiting pointer path arithmetic to find a special node — is the same. Cycle II even uses a similar meeting-point argument to locate the cycle entrance.

Palindrome Linked List (LeetCode 234) and Maximum Twin Sum (LeetCode 2130) use the slow/fast pointer technique for a different purpose: finding the midpoint to enable reversal and pair-wise processing. These problems share the two-pointer family membership but apply the technique structurally rather than analytically.

Together, Linked List Cycle, Intersection of Two Linked Lists, Palindrome Linked List, and Maximum Twin Sum form the linked list pointer family. Each problem exploits a two-pointer invariant — cycle detection, path equalization, midpoint finding, or twin alignment. Mastering the arithmetic behind each invariant lets you recognize and solve any member of this family quickly in interviews.