160 - Intersection of Two Linked Lists

Difficulty: Easy | Pattern: Two Pointers | Company tags: Amazon, Microsoft, Facebook, Bloomberg

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.

The intersection is by reference, not value — the node objects are the same.

Example:

listA: a1 → a2 →
                  c1 → c2 → c3
listB:      b1 → b2 →

Input: headA = [4,1,8,4,5], headB = [5,6,1,8,4,5], intersectVal = 8
Output: Reference to node with value 8

Approach: Two Pointers with List Switching — O(m+n), O(1)

Key insight: If pointer A walks list A then list B, and pointer B walks list B then list A, both pointers travel the same total distance (m + n). They'll meet at the intersection node (or both reach None if no intersection).

def getIntersectionNode(headA, headB):
    a, b = headA, headB
    
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    
    return a  # either intersection node or None

Algorithm Flow

Why This Works

• List A length: a_len (unique part: m, shared: k)
• List B length: b_len (unique part: n, shared: k)
• Pointer A travels: m + k + n steps
• Pointer B travels: n + k + m steps

Both travel the same distance, so they arrive at the intersection simultaneously. If no intersection, both reach None at the same time.

Dry Run

listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], intersection at node 8

• m = 2 (nodes 4,1 before intersection), n = 3 (nodes 5,6,1 before intersection), shared = 3

Steps	a	b
0	4	5
1	1	6
2	8	1
3	4	8
4	5	4
5	headB(5)	5
6	6	headA(4)
7	1	1
8	8	8

Meet at node 8 ✓

Alternative: Hash Set — O(m+n), O(m)

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

Edge Cases

• No intersection → both pointers reach None simultaneously → return None
• Both lists of same length → they meet immediately at the shared node (or never)
• Intersection at head of one list

Complexity

Approach	Time	Space
Two pointers	O(m+n)	O(1)
Hash set	O(m+n)	O(m)

Key Terms

Term	Definition
Two pointers	Two references traversing structures simultaneously to find a relationship (here, a meeting point) in linear time.
Pointer switching	Redirecting a pointer to the other list's head once it exhausts its own list, equalizing total distance traveled.
Reference equality	Comparing node identity (not value) to detect the true intersection, since values can coincide by chance.
Traversal length equalization	The technique of making both pointers cover m + n total nodes so they align at the intersection regardless of individual list lengths.

FAQ

Q: Can this be solved without extra space? A: Yes, the two-pointer switching approach uses O(1) space. The hash set alternative trades O(1) space for O(m) space to avoid the double pass logic.

Q: What if the input lists don't intersect? A: Both pointers traverse m + n nodes total and reach None at exactly the same step, so the loop condition a != b becomes None != None → false, correctly returning None.

Q: What if the lists intersect but have very different lengths? A: It doesn't matter — the pointer switching guarantees both pointers travel the exact same total distance (m + n), so they always reach the intersection node simultaneously, even for wildly skewed lengths.

Q: How would this change if the lists could be circular? A: Reference-based traversal would loop forever without a visited check. You'd first need cycle detection (Floyd's algorithm) before applying an intersection strategy, since the current solution assumes both lists terminate in None.

Q: Why not just compare node values instead of computing lengths? A: Values can be duplicated across unrelated nodes, giving false positives. Comparing lengths (or using the switching trick) or comparing identity avoids that ambiguity entirely.

Quick Revision

• Problem: find the exact node where two singly linked lists merge (by reference, not value).
• Core trick: pointer a walks A then B; pointer b walks B then A — both cover m + n nodes.
• They meet at the intersection node, or both hit None together if there's no intersection.
• Time: O(m+n); Space: O(1).
• Alternative: hash set of all of list A's nodes, then scan B for a hit — O(m+n) time, O(m) space.
• Alternative: compute length difference, advance the longer list's pointer first, then walk both together.
• Edge case: identical lengths — pointers might meet on the first comparison.
• Edge case: no intersection — loop terminates when both pointers become None.
• Compare by identity (is/== on node objects), never by value.

Related Problems

• 141 - Linked List Cycle — shares the two-pointer traversal technique on singly linked lists.
• 142 - Linked List Cycle II — uses similar pointer-meeting logic to find a specific node.
• 21 - Merge Two Sorted Lists — same family of problems manipulating two linked-list traversals simultaneously.