Where Two Linked Lists Meet
Updated
Problem statement
Think of memory as a row of n numbered node slots, 0 to n - 1. Slot i holds one node, and next[i] tells you which slot holds the node after it; -1 means the list ends there. Following next from slot headA spells out list A, and following it from slot headB spells out list B.
When the two walks land on a common slot, they continue through exactly the same slots to the end, so the shared part looks like the tail of the letter Y. Find the slot where that shared tail begins and return its number. If list A and list B have no slot in common, return -1.
Slots are compared by their numbers only. A list may also begin on a slot of the other list; that slot is then the answer.
Function
findMeetingNode(next: int[], headA: int, headB: int) → intExamples
Example 1
next = [2,3,4,2,-1,0]headA = 5headB = 1return = 2Walking from slot 5 gives 5 -> 0 -> 2 -> 4; walking from slot 1 gives 1 -> 3 -> 2 -> 4. Both lists go through nodes 2 and 4, and node 2 is the first node they share, so the answer is 2.
Example 2
next = [2,3,-1,4,-1]headA = 0headB = 1return = -1From slot 0 the walk is 0 -> 2, and from slot 1 it is 1 -> 3 -> 4. No slot appears in both walks, so the answer is -1.
Example 3
next = [2,0,-1,1]headA = 3headB = 0return = 0From slot 3 the walk is 3 -> 1 -> 0 -> 2. The second walk begins at slot 0, which the first walk already passes through, and continues 0 -> 2. The first shared node is list B's own head, so the answer is 0.
Constraints
1 <= n <= 2000, wheren = next.length-1 <= next[i] <= n - 10 <= headA, headB <= n - 1- Following
nextfromheadA, and fromheadB, reaches-1without visiting any node twice. - Every node is on list A, on list B, or on both.