Cycle in a Sequence Chain

Problem Statement

You're given a chain of nodes, represented as an array of "next" pointers: next_index[i] tells you which node comes after node i, or that node i is the end of the chain (-1). Starting from a given head node and repeatedly following these pointers, determine whether the chain eventually loops back on a node it has already visited — in which case it would go on forever — or whether it terminates cleanly by reaching -1. Print true if there's a cycle, false if the chain terminates.

Input Format

The input has exactly three lines:

• Line 1: a single integer n, the number of nodes.
• Line 2: n space-separated integers, next_index[0] through next_index[n-1], each either -1 or a valid node index.
• Line 3: a single integer, the head — the node to start following the chain from.

Output Format

Print exactly one line containing the word true or the word false, in lowercase with no surrounding quotes or extra text. Print true if following the chain from head ever revisits a node, and false if it instead reaches -1.

Example Walkthrough

Take the first sample: next_index = [1, 2, 3, 1], head 0. Following the chain by hand: start at node 0. next_index[0] = 1, so move to node 1. next_index[1] = 2, move to node 2. next_index[2] = 3, move to node 3. next_index[3] = 1, move to node 1 — but node 1 has already been visited earlier in this walk. Since the chain has led back to a node already seen, it will keep cycling through 1, 2, 3 forever without ever reaching -1, so the answer is true.

Now picture the same chain traced with two pointers, slow and fast, both starting at node 0. Round 1: slow moves one step to node 1; fast moves two steps, first to node 1, then to node 2 — so fast is at node 2. They don't match yet. Round 2: slow moves from 1 to 2; fast moves two steps from 2: to node 3, then to node 1 — fast is now at node 1. Still no match (slow at 2, fast at 1). Round 3: slow moves from 2 to 3; fast moves two steps from 1: to node 2, then to node 3 — fast is now at node 3, the same node as slow. The two pointers have met, confirming a cycle, matching the direct trace above.

Approach

The most direct way to detect a cycle is to walk the chain one node at a time, remembering every node visited so far in a set. The moment the chain arrives at a node already in that set, there's a cycle; if instead it reaches -1, there isn't. This is correct and easy to reason about, but it uses extra memory proportional to how many nodes get visited before an answer is found.

The two-pointer (or "tortoise and hare") technique gets the same answer without that extra memory. Start both a slow pointer and a fast pointer at head. On each round, move the slow pointer forward by one step and the fast pointer forward by two steps (checking along the way whether the fast pointer has run off the end at -1, in which case the chain terminates and there's no cycle). If the chain has no cycle, the fast pointer will always reach -1 first, since it's covering ground twice as quickly. But if the chain does loop, both pointers eventually end up going around the same finite loop repeatedly — and because the fast pointer gains on the slow one by exactly one extra step every round, the gap between them (measured around the loop) shrinks by one step each round until it hits exactly zero, meaning the two pointers land on the very same node at the same time. That meeting point is only possible if a cycle exists, so detecting it is enough to answer true — there's no need to figure out where the cycle starts or how long it is.

Because the slow pointer only ever takes one step at a time and the chain (if it has a cycle) is made up of at most n distinct nodes, the two pointers are guaranteed to either meet or have the fast pointer hit -1 within at most n rounds, giving O(n) time using only a fixed amount of extra memory for the two pointer positions.

Common Mistakes

• Checking slow == fast before either pointer has moved. Both pointers start at the same node (head) by definition, so comparing them before the first move always looks like a match — the comparison needs to happen only after both pointers have taken their steps for the round.
• Moving the fast pointer two full steps without checking for -1 in between. If the fast pointer's first step already lands on -1, trying to take the second step (looking up next_index[-1], which isn't a valid index at all) either crashes or, in a language that quietly allows negative indexing, wraps around to some unrelated node — both are wrong. The fast pointer's path to -1 needs to be checked after each individual step, not just at the end of the round.
• Not handling a node whose next pointer points to itself. A single node with next_index[i] = i is a valid one-node cycle — the very first round should have both pointers immediately land back on that same node and correctly report true, rather than this edge case being treated as a special "no cycle" situation.