Intersection point of two linked lists (shared node)
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
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;}