Intersection point of two linked lists (shared node)

Easy

Problem

Two singly linked lists merge at some node and share every node after it (a Y shape). Return that first shared node, or null if they never meet. Compare nodes by identity, not by value.

Example 1

Input:  A: 4 → 1 ↘ 8 → 4 → 5,  B: 5 → 6 → 1 ↗ (same 8)
Output: node 8

Also asked as: Intersection Point of two Linked Lists

Test cases

Case 1

Input:    [[4,1],[5,6,1],[8,4,5]]
Expected: 8

Case 2

Input:    [[1,9,1],[3],[2,4]]
Expected: 2

Case 3

Input:    [[2,6,4],[1,5],[]]
Expected: null

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Two pointers, swap heads at the end

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

Advance pA and pB one step at a time; when one hits null, redirect it to the other list’s head. They meet at the intersection after at most n+m steps (or both at null).

function getIntersectionNode(a, b) {
let pA = a, pB = b;
while (pA !== pB) {
pA = pA ? pA.next : b;
pB = pB ? pB.next : a;
}
return pA; // node or null
}

2. Length difference

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

Measure both lengths, advance the longer list by the difference, then move both together until they match.

function getIntersectionNode(a, b) {
const len = (h) => { let n = 0; while (h) { n++; h = h.next; } return n; };
let la = len(a), lb = len(b);
while (la > lb) { a = a.next; la--; }
while (lb > la) { b = b.next; lb--; }
while (a !== b) { a = a.next; b = b.next; }
return a;
}