Standard Bar Linked List · Medium Problems of LL O(N) · O(1)
A mis-coupled conveyor loop has been confirmed, and maintenance now needs the exact station where the return path re-enters the line — that is where to cut. The two-probe rig already locates a meeting point inside the loop; a phase-distance argument then says that resetting one probe to the line's start and marching both one step at a time makes them converge precisely at the re-entry station.
Input: An array head of node values and an integer pos — the 0-based index the tail's next pointer connects to, or -1 when there is no loop.
Output: The 0-based index of the node where the cycle begins, or -1 when the list has no cycle.
0 <= list length <= 10^4-10^5 <= pos <= list length - 1-10^9 <= node value <= 10^9Input: {"head":[3,2,0,-4],"pos":1}
Output: 1
The tail reconnects to index 1, so the loop begins at the node holding 2.
Input: {"head":[1,2],"pos":0}
Output: 0
The tail re-enters at the head itself.