Why it works
- Every value is from 1 to n, so every link leads to a real index and none leads to 0: from 0 the links go on forever, through at most n + 1 indices, so they end in a loop.
- The loop starts at the index two links lead into: one from the tail and one from the end of the loop. Two cells hold that index, so it is the duplicate.
- Finding where a loop starts is Linked List Cycle II: meet inside, send slow back to the start, step both by one. The array is only read, and two indices are all the memory.
Complexity
Time O(n): each loop takes at most about n steps, as in Linked List Cycle II. Memory O(1): two indices, and the array is not changed.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗