Find the Node Where Two Linked Lists Intersect

Given the heads of two singly linked lists, head1 and head2, they may intersect at some node and share every node after that (a "Y" shape) — or they may never intersect at all. Find the value at the first shared node, or return -1 if the lists don't intersect. Because this exercise is auto-graded by comparing plain output values, the function returns the intersection node's value rather than the node itself — but the algorithm underneath still has to reason about node identity, not value. Two different nodes in two different lists could coincidentally hold the same number without being the same node; the real question is whether the lists ever converge onto literally the same chain of memory. The brute-force check makes that identity check explicit — for every node of head1, scan all of head2 for a node that is it (not just equals it). The optimal solution reaches the same guarantee in one pass each with a neat trick: walk both lists with one pointer apiece, and whenever a pointer falls off the end of its own list, send it to the other list's head instead of stopping. That head-switch evens out any difference between the two lists' own lengths, so both pointers arrive at the shared node — or at null, together, if there is none — after at most one switch each.

Test Case 1:

Input:head1 = [2, 8, 5], head2 = [9, 9] joining head1 at node 8

Output:8

Explanation:head1 and head2 are two separate chains that merge into the same tail (8 -> 5) — 8 is the first shared node.

Test Case 2:

Input:head1 = [2, 6, 4], head2 = [1, 5], no shared node

Output:-1

Explanation:Two completely separate lists that never meet.

Test Case 3:

Input:head1 = [1, 2, 3], head2 joins head1 right at its head

Output:1

Explanation:head2 has no nodes of its own — it IS head1, so they "intersect" at the very first node.

Constraints

◆0 ≤ number of nodes unique to head1 or head2 ≤ 10
◆0 ≤ number of nodes shared by both lists ≤ 10
◆-1000 ≤ node value ≤ 1000
◆If the lists intersect, they always share a common tail (a "Y" shape) — once they meet at a node, every node after that is identical in both lists

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

head1's own values — 0-6 integers, allow emptyhead2's own values — 0-6 integers, allow emptyshared tail values — 0-6 integers — empty means no intersection

1	class Solution {
2	public int getIntersectionNodeValue(Node head1, Node head2) {
3	Node a = head1;
4	Node b = head2;
5	while (a != b) {
6	a = (a == null) ? head2 : a.next;
7	b = (b == null) ? head1 : b.next;
8	}
9	return (a == null) ? -1 : a.val;
10	}
11	}
12

Linked List

2

a

8

5

null

Linked List

9

b

9

8

5

null

Variables

a2

b9

INITIALIZE

a starts at head1, b starts at head2. head1's own portion has 1 node (2); head2's own portion has 2 nodes (9, 9) — the mismatch is exactly why a plain 'walk both together' wouldn't line up.

Step 1 / 21

Approach & Solutions

Brute Force — Nested Comparison of Node References

Good

For every node in head1, walk the entirety of head2 checking whether any node there is the exact same node in memory — not just an equal value, the same physical node. The first match found is the intersection. If head1 runs out with no match ever found, the lists never meet. Correct, but re-walking all of head2 for every single node in head1 is wasteful when both lists only need to be walked once each.

TimeO(n · m)

SpaceO(1)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public int getIntersectionNodeValue(Node head1, Node head2) {
        Node a = head1;
        while (a != null) {
            Node b = head2;
            while (b != null) {
                if (a == b) {
                    return a.val;
                }
                b = b.next;
            }
            a = a.next;
        }
        return -1;
    }
}

Optimal — Two Pointers, Switch Heads

Optimal

Walk a from head1 and b from head2, one step at a time. Whenever a pointer runs off the end of its own list, redirect it to the OTHER list's head instead of stopping. This equalizes the distance each pointer travels: by the time either pointer reaches the intersection (or the end, if there is none), both have covered exactly the same total distance — head1's length plus head2's length — so they arrive at the shared node (or at null) at the same moment. Only one switch per pointer is ever needed.

TimeO(n+m)