Linked Lists
When an array is secretly a linked list
If a value can be read as an index, an array becomes a list, and cycle detection applies to it.
Key idea
The reframe
An array whose values are all valid indexes into itself defines a walk: stand at index i, and the next index is the value stored there. That is exactly a linked list, with no nodes allocated anywhere.
Since the walk never leaves the array and the array is finite, it must eventually revisit a position. So this implicit list always contains a cycle, and the tools from the fast-and-slow lesson apply unchanged.
Tip
Read that walk
Starting at index 0, the walk goes 0, 1, 3, 2, 4, and then repeats 2, 4 forever. The cycle is entered at index 2, and the value that leads into it from two different places is what a duplicate looks like in this framing.
Two different positions pointing at the same next position is precisely a repeated value, which is why cycle detection answers a question that appears to be about duplicates.
Why it works
Finding where the cycle begins
Detecting a cycle is the easy half. Finding its entrance needs a second phase, and the fact behind it is worth stating precisely.
Let the distance from the start to the cycle entrance be a, and let the meeting point of the two pointers sit b steps into the cycle. When they meet, the fast pointer has traveled exactly twice as far as the slow one, and working that equality through shows that a equals the distance from the meeting point back around to the entrance.
So: after they meet, move one pointer back to the start and advance both one step at a time. They meet again exactly at the entrance.
The first phase is the same loop from three lessons ago, reading values[i] where you previously read node.next. Here it is on the array above, printing where the two pointers stand after each step.
Gotcha
The answer is a position, and sometimes a value
The second phase hands you an index. Whether the problem wants that index or the value stored there depends on how the array was set up, and the two are easy to confuse because both are small integers.
Trace a tiny example by hand and check which one matches the expected answer. This is the kind of detail that produces a solution that is right in structure and wrong in output.
Edge cases
The second phase compares before moving, or after
Write the second phase so that it advances both pointers and then compares. That works because the first phase leaves them somewhere other than the start. Comparing first would return the meeting point immediately in the case where it happens to equal the starting position.
Both orderings appear in published solutions and they differ on exactly one input shape. Trace the smallest cycle you can construct to confirm whichever you write.
Why this problem is in a linked list unit
It has no linked list in it. It is here because the technique is the one from three lessons ago, and the entire difficulty is noticing that the array can be read as one.
That noticing is the skill worth having. When a problem forbids modifying the input and forbids extra space, and involves values that happen to be valid indexes, this reframe is what is being asked for.
Why must a cycle exist?
In an array of length n whose values are all valid indexes, why is the walk guaranteed to cycle?
Find The Duplicate Number
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.