data-structures · intermediate · ~25 min
Floyd's tortoise-and-hare algorithm (two pointers, different speeds).
Given the head of a singly-linked list with typedef struct node { int v; struct node *next; } node_t;, return 1 if it has a cycle, 0 otherwise. Implement int has_cycle(node_t *head).
Floyd's tortoise-and-hare is the canonical example of using rates to find structure: it's used to detect cycles in CPU instruction traces, in random number generators, and in serialization graphs.
A pointer to the head (may be NULL).
1 if cycle exists, 0 otherwise.
O(1) auxiliary memory. No malloc. No mutating the list.
typedef struct node { int v; struct node *next; } node_t;
int has_cycle(node_t *head) { /* TODO */ return 0; }
Comparing slow != fast before stepping (causes false positive when head==head); not checking fast->next before stepping fast twice (NPE on linear lists); using a hash set when O(1) memory is required.
NULL head. Single node, no cycle. Single node, self-loop. Two-node cycle.
O(n) time, O(1) memory.
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.