Linked List Cycle (Fast and Slow Cursors)

core

A singly linked list is given the same way list-reverse-next gives it: nodes are numbered 0 through n-1, next[u] holds the index of the node after u or -1 when u has no successor, and head is the index of the first node. One guarantee is different here: the walk from head is not promised to terminate. It either reaches a node whose next is -1, or it re-enters a node it already passed and loops forever.

Implement has_cycle(next, head): return whether the walk from head loops, using two cursors and no extra memory. slow steps one link at a time, fast steps two; on a looping list fast laps slow inside the cycle and they land on the same node, and on a terminating list fast runs off the end first. The drill is the loop body's order: advance both cursors first, then compare. Both cursors start at head, so they are equal before they ever move; compare before advancing and every list on earth reports a cycle on the spot. The guard belongs on fast: keep going only while fast is a node and next[fast] is a node, so the two-step never reads a link off the end of the list.

Example: with next = {1, 2, -1} and head = 0 the walk is 0 -> 1 -> 2 and stops: no cycle. With next = {1, 2, 1} and head = 0 the walk is 0 -> 1 -> 2 -> 1 -> 2 -> ...: has_cycle returns true. In the first list, the compare-before-advance version still answers true, because slow and fast sit together on node 0 before the first step.

Input format: each test in tests/*.in is laid out as:

Line 1: n, the number of nodes; nodes are numbered 0 to n - 1.
Line 2: the n entries of next, where the i-th is the index node i points to, or -1 for none.
Line 3: head, the start node.

Test 02.in reads:

1
0
0

This is a single node whose next is itself (next[0] = 0), starting at node 0: the tightest possible cycle.

Where you'll use it:

✦ Solution & editorial unlock with the pass.