DSA problem
Intersection of Two Linked Lists
Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
The intersection is defined by reference, not by value: two lists intersect when they share the exact same node object from some point onward. After the intersection point, the two lists share every subsequent node. The structure of each list must remain unchanged after your function returns, and you may assume there are no cycles anywhere in the structure.
A naive approach would compare every node in list A against every node in list B, costing O(m * n) time. A better idea uses a hash set: walk list A storing each node reference, then walk list B and return the first node already in the set, taking O(m + n) time but O(m) extra space.
The optimal trick uses two pointers and exploits a clean algebraic identity. Let pointer pA traverse A then B, and pB traverse B then A. Each pointer travels exactly lenA + lenB nodes before reaching the end, so after at most that many steps they either meet at the intersection node or both reach null simultaneously. This switching of tracks neutralizes the length difference between the lists, giving an O(m + n) time, O(1) space solution.
Examples
intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3Intersected at '8'intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1Intersected at '2'intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2No intersectionConstraints
- The number of nodes of listA is in the range [1, 3 * 10^4].
- The number of nodes of listB is in the range [1, 3 * 10^4].
- 1 <= Node.val <= 10^5
- There are no cycles anywhere in the entire linked structure.
- The lists must retain their original structure after the function returns.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.