Does the chain loop back
Detect a loop by letting a fast runner chase a slow one: if there is a loop, the fast one eventually laps and catches the slow one. About 16 minutes.
Chasing in a circle
A chain with a loop at the end never reaches the end: following next goes round and round. How can you tell? Send two runners along it, one stepping one node at a time and the other two.
If the chain has no loop, the fast runner runs off the end and you're done. If there is a loop, both end up circling inside it, and the fast runner gains one step per round on the slow one. So it must catch up and land on the same node.
slow = fast = start
while fast != -1 and nxt[fast] != -1:
slow = nxt[slow]
fast = nxt[nxt[fast]]
if slow == fast:
return True
return FalseBoth runners start at node 0.
Chains as a list of positions
A loop can't be given as a plain list of values, so here the chain is described by positions. An array called nxt tells you, for each node, the position of the node that follows it, or -1 if it is the last. The walk starts at a given position.
Moving a runner one step means looking up where its node points. Two steps means looking up twice, but only after checking that the runner and the node after it exist.
slow = nxt[slow] fast = nxt[nxt[fast]]
Fast runs to a node whose next is -1. What do you answer?
- ANo loop: the chain ends
- BThere is a loop
- CKeep going
Show the answer
No loop: the chain ends. A loop never ends, so reaching the end proves there is no loop.
Does the chain loop back
A chain of nodes numbered 0 to n − 1 is described by an array nxt: nxt[i] is the number of the node that follows node i, or -1 if node i is the last node of the chain. Starting at node start, follow the chain. Return true if you ever come back to a node you have already been on (the chain contains a loop), and false if the chain ends.
nxt = [1, 2, 3, 4, 2], start = 0 → true
1 ≤ n ≤ 100,000 · nxt[i] is -1 or a node number · 0 ≤ start < n