Where the loop begins

A linked list may point back at one of its own nodes. Report the position of the node where the loop begins, counting the head as position 0. If the list simply ends, report -1.

Worked example#

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          +---------+

The loop begins at the 3, which is position 2.

The idea#

Run the two walkers until they meet. Then do something that looks like a trick until you have seen why it works: move one walker back to the head, and step both one at a time. Where they meet again is the start of the loop.

Why that works#

Call a the number of steps from the head to the start of the loop, b the steps from there to where they met, and c the rest of the loop. The loop is b + c long.

When they meet, the slow walker has taken a + b steps and the fast one has taken twice that. The fast one has also gone round the loop some whole number of times, so:

2(a + b) = a + b + k(b + c)      for some whole k
    a + b = k(b + c)
        a = k(b + c) - b

Read the last line as a sentence: stepping a times from the meeting point lands on the start of the loop, because it goes round k times and then comes up b short. And stepping a times from the head also lands on the start, by definition of a.

So two walkers, one from the head and one from the meeting point, moving at the same speed, arrive together. Nobody needs to know what a is.

Constraints#

• 0 <= n <= 100000

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.