Intersection of Two Linked Lists

The key idea

Once two lists merge they share the SAME nodes to the end, so the answer is a node-identity question, not a value question. The two-pointer trick: walk pA over A-then-B and pB over B-then-A. Both traverse exactly m + n nodes, so after the swap they land on the same node — the intersection — or both hit null together.

Problem

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 two lists may share a common suffix: from the node where they meet, they are the same nodes all the way to the end. Note that the intersection is defined by node reference, not by node value — two nodes with equal values are not the intersection unless they are the very same node. It is guaranteed that there are no cycles anywhere in the entire linked structure. The lists must retain their original structure after the function returns.

Constraints

The number of nodes of listA is in the range [0, 3 * 10^4].
The number of nodes of listB is in the range [0, 3 * 10^4].
1 <= Node.val <= 10^5
0 <= skipA < m
0 <= skipB < n
intersectVal is 0 if there is no intersected node, otherwise it is the value of the intersected node.
If listA and listB have no intersection, then intersectVal is 0.

Examples

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 Output: Intersected at '8'

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Output: Intersected at '2'

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: No intersection

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →