Intermediate Open Free

Linked List Intersection

You are given the heads of two singly linked lists, headA and headB. The two lists may converge into a shared tail (i.e., after some point, the same physical nodes are shared by both lists), or they may not intersect at all. Return the node at which the two lists intersect, or None if they do not intersect. Intersection is defined by node identity (the same node object), not by equal values.

A:  a1 -> a2
              \
                c1 -> c2 -> c3 -> None
              /
B:  b1 -> b2 -> b3

Here headA and headB intersect at node c1.

Example 1

A: 4 -> 1 -\
             8 -> 4 -> 5 -> None
B:      5 -> 6 -> 1 -/
Output: node with value 8 (the intersection node)

Example 2

A: 1 -> 2 -> None
B: 3 -> 4 -> None
Output: None (no intersection)

Constraints

Combined node count across both lists is at most 3 * 10^4.
The lists themselves are guaranteed to be acyclic (no cycles).
Aim for O(n + m) time and O(1) extra space — do not use extra data structures like a hash set of visited nodes.

Solution

If the lists intersect, they share the exact same tail from the intersection point onward, but they can differ in length before that point. A hash-set-of-visited-nodes approach solves this in O(n + m) time but O(n) space; the O(1)-space trick is a clever pointer-swap.

Walk two pointers, one starting at headA and one at headB. When a pointer reaches the end of its own list, redirect it to the head of the other list instead of stopping. Because len(A) + len(B) is the same regardless of which list you started from, both pointers will have traveled the same total distance by the time they either meet at the intersection node or both become None simultaneously (no intersection).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def get_intersection_node(
    headA: ListNode | None, headB: ListNode | None
) -> ListNode | None:
    if headA is None or headB is None:
        return None

    ptr_a, ptr_b = headA, headB
    while ptr_a is not ptr_b:
        ptr_a = ptr_a.next if ptr_a is not None else headB
        ptr_b = ptr_b.next if ptr_b is not None else headA

    return ptr_a  # either the intersection node, or None

Why it works: if the lists intersect, both pointers traverse len(A) + len(B) - len(shared tail) nodes before landing on the intersection node together. If they don't intersect, both pointers independently traverse len(A) + len(B) nodes and land on None together, ending the loop with ptr_a is ptr_b is None.

Complexity: O(n + m) time, where n and m are the two list lengths — each pointer traverses at most both lists once. O(1) extra space, since only two pointer variables are used.

Share this question

Share on X Share on LinkedIn

← Back to Linked Lists practice