Linked Lists and Cycle Detection, Explained

An array stores its elements next to each other in memory, so getting element i is one arithmetic step: jump to start + i * size. A linked list gives that up — each element (a "node") stores its value plus a pointer to the next node, scattered wherever memory happened to have room. Getting to element i means following i pointers one at a time, $O(n)$ instead of $O(1)$ . What you gain is $O(1)$ insertion and deletion anywhere you already have a pointer to, with no shifting of the rest of the list, which is why linked lists still show up under the hood of queues, LRU caches, and some hash table implementations.

The idea: a chain of nodes, each pointing at the next

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

A list is just a reference to its first (head) node; walking it means following .next until you hit None. Nothing stops a bug — or an intentional cyclic structure — from making some node's .next point back to an earlier node instead of ending at None. Naively walking such a list never terminates.

Worked example: Floyd's tortoise and hare

Use two pointers moving at different speeds: slow advances one node per step, fast advances two. If there's no cycle, fast reaches None first and you're done. If there is a cycle, fast eventually laps slow from behind and they land on the same node — proof of a loop, using only two extra pointers, $O(1)$ space, no need to store every node visited.

Take the list 1 → 2 → 3 → 4 → 5 → 3 (node 5 points back to node 3, forming a cycle of length 3):

step	slow	fast
start	1	1
1	2	3
2	3	5
3	4	4 (5→3→4)
4	5	3 (4→5, then 3)
5	3	3

At step 5, slow and fast both land on node 3 — a match confirms a cycle exists. Why they must eventually meet: once slow enters the cycle, fast is already inside it and gains one node of relative distance on slow every step (moving 2 vs 1), so the gap between them shrinks by 1 each step and must hit exactly 0 within one full lap of the cycle.

def has_cycle(head):                # O(n) time, O(1) space
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Once both pointers are inside the loop, the faster one gains one step per round on the slower one, so they must collide somewhere inside the cycle — there's no way for a strictly-faster pointer to permanently avoid a finite loop.

Floyd's algorithm detects a cycle in $O(n)$ time with $O(1)$ extra space — no set of visited nodes required. Compare against the simpler alternative of storing every visited node in a hash set, also $O(n)$ time but $O(n)$ space; the two-pointer trick trades a bit of cleverness for memory.

Where it shows up

Interviewers ask for cycle detection directly (LeetCode's "Linked List Cycle"), and as a follow-up, finding the cycle's starting node — a second phase of the same two-pointer technique, worth knowing cold since it's a common extension. In production systems, cyclic references matter beyond literal linked lists: a dependency graph with an accidental cycle, a circular reference in a config or object graph, or a corrupted pointer-based data structure in a low-latency C++ system can all hang a process the same way an unguarded linked-list walk would — recognizing the pattern is what lets you add the right guard before it ships.

Linked Lists and Cycle Detection

The idea: a chain of nodes, each pointing at the next

Worked example: Floyd's tortoise and hare

Where it shows up

Related concepts

Practice in interviews

Further reading