Detect a cycle in a linked list

Challenge

Detect whether a singly-linked list contains a cycle.

Task

Given the head of a singly-linked list whose nodes are typedef struct node { int v; struct node *next; } node_t;, implement int has_cycle(node_t *head) that returns 1 if following next pointers ever loops back into a node already visited, else 0.

Input

head: a pointer to the first node (the type node_t is given, with an int v and a next pointer). May be NULL.

Output

int: 1 if the list has a cycle, 0 if it ends at NULL.

Example

1 -> 2 -> 3 -> 4 -> NULL        ->   0
1 -> 2 -> 3 -> 4 -> back to 2   ->   1
NULL                            ->   0
node whose next points to itself ->  1

Edge cases

• NULL head returns 0.
• A single node with next == NULL returns 0; a single node pointing to itself returns 1.

Rules

• Use O(1) memory (Floyd's two-pointer method). Do not malloc, do not mutate the list.

Why this matters

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.

Input format

head: pointer to the first node_t (given: int v; node_t *next;); may be NULL.

Output format

int: 1 if a cycle exists, else 0.

Constraints

O(1) auxiliary memory. No malloc. No mutating the list.

Starter code

typedef struct node { int v; struct node *next; } node_t;
int has_cycle(node_t *head) { /* TODO */ return 0; }

Common mistakes

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.

Edge cases to handle

NULL head. Single node, no cycle. Single node, self-loop. Two-node cycle.

Complexity

O(n) time, O(1) memory.

Background lessons

• Linked lists
• The two-pointer technique