Intersection of Two Linked Lists

EasyLinked List · Two Pointers🧩 Linked List Techniques LeetCode #160 ↗Updated Oct 30, 2026

Problem

Two singly linked lists may merge at some node and share every node after it (a Y shape). Return the first shared node (same object, not just same value), or null if they never meet. The lists have no cycles and must be left unchanged.

InputA=[4,1,8,4,5], B=[5,6,1,8,4,5]Outputnode 8 (tail [8,4,5] shared)

InputA=[2,6,4] B=[1,5]Outputnull

1 ≤ m, n ≤ 3·10⁴ · 1 ≤ Node.val ≤ 10⁵ · Follow-up: O(m+n) time, O(1) memory.

Try it yourself

Java

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

If pointer a walks A then B, and b walks B then A, both travel exactly m+n steps — so they line up on the shared tail and reach the merge node (or null) together.

PatternLinked List Techniques

Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.

Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.

Open the Linked List Techniques guide →

Approaches

Brute ForceCompare Every Pair of Nodes

Time O(m·n)Space O(1)

For each node of A, scan all of B looking for the same reference. The first node of A that appears in B is the merge point, since everything after it is shared.

Java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    for (ListNode a = headA; a != null; a = a.next) {
        for (ListNode b = headB; b != null; b = b.next) {
            if (a == b) return a; // same object, not same value
        }
    }
    return null;
}

No extra memory, but quadratic — ~9·10⁸ checks at max size.

BetterHash Set of Nodes

Time O(m+n)Space O(n)

Store every node of B (by identity) in a HashSet, then walk A; the first node already in the set is the intersection. This trades memory for an O(1) membership test.

Java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> nodesInB = new HashSet<>();
    for (ListNode b = headB; b != null; b = b.next) nodesInB.add(b);
    for (ListNode a = headA; a != null; a = a.next) {
        if (nodesInB.contains(a)) return a;
    }
    return null;
}

Linear time, but O(n) extra memory fails the follow-up.

OptimalTwo Pointers — Switch Heads

Time O(m+n)Space O(1)

Let the lists be A = x + c and B = y + c (c = shared tail). When a pointer falls off its list, restart it at the other head. After x + c + y steps both stand on the merge node; with no merge (c = 0) both hit null after m + n steps and the loop ends.

Java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    return a; // merge node, or null if none
}

Linear time, O(1) memory, no length counting — answers the follow-up.

Pro tip

Alternative O(1) idea: count both lengths, advance the longer list by the difference, then step together until the pointers meet.

At a glance

Level	Approach	Time	Space
Brute Force	Compare Every Pair of Nodes	`O(m·n)`	`O(1)`
Better	Hash Set of Nodes	`O(m+n)`	`O(n)`
Optimal	Two Pointers — Switch Heads	`O(m+n)`	`O(1)`

Common pitfalls

Comparing a.val == b.val — equal values don't mean a shared node.
Switching to the other head on a.next == null — skips the null step and loops forever with no merge.
Mutating the lists (e.g. marking or reversing) — the problem forbids it.

Interview tips

Clarify that intersection means node identity, not value.
Prove termination: both pointers take at most m+n+1 steps.
Mention the length-difference variant as an equally valid O(1) answer.

Pattern

Equalise path lengths → aligning two pointers on lists of different lengths.

My notes saved in this browser