Does this list loop back on itself

A singly linked list either ends, or one of its nodes points back at an earlier node so that following next goes round for ever. Say whether it loops.

Worked example#

3 -> 2 -> 0 -> -4
     ^           |
     +-----------+

The last node points back at the 2, so this loops and the answer is true.

The idea#

The tempting answer is to remember every node you have seen and stop when one comes round again. That works, and it costs memory proportional to the length of the list.

There is a way that uses two variables and nothing else. Send two walkers down the list: a slow one taking a single step at a time, and a fast one taking two.

If the list ends, the fast walker runs off the end and you are done: no loop.

If the list loops, the fast walker cannot run off the end, because there is no end. Both walkers end up going round the loop for ever, and the fast one gains exactly one position on the slow one every step. A gap that shrinks by one each step must reach zero, so they land on the same node, and that meeting is the proof.

They cannot step over each other, which is the part worth pausing on: the gap goes 3, 2, 1, 0. It never skips from 1 to -1, because the fast walker closes the gap by exactly one per step.

Constraints#

• 0 <= n <= 100000
• Values may repeat, so you cannot decide anything by comparing values

About the input#

The list is written as a count, then the values, then one more number saying which position the last node points back to. -1 means the list simply ends. You are handed the head with the links already made.