Linked List Cycle: why Floyd's tortoise catches the hare

The problem gives you the head of a linked list and asks one thing: does following next pointers ever loop back? The cycle could close at the very first node, somewhere in the middle, or not at all. You cannot measure the list's length from outside — there is no length field — so you have to discover the answer by walking.

The list [3, 2, 0, -4] with a back-edge from -4 to node 2 is Example 1. That back-edge is invisible from outside — you only find it by noticing you have arrived at a node you have already seen.

The problem

Given the head of a linked list, determine whether the list contains a cycle — that is, whether following next pointers from any node eventually leads back to a node already visited. Full statement: LeetCode 141.

Constraints:
- The number of nodes in the list is in the range [0, 10^4].
- -10^5 <= Node.val <= 10^5
- pos is -1 or a valid index in the linked list.

What the constraints actually force

The node count sits in [0, 10^4]. That is small enough that an O(n) solution is fine on time, but the follow-up makes the design question explicit: can you do it in O(1) space?

The value range [-10^5, 10^5] is irrelevant to the algorithm — you are comparing node identity (memory address), not node values. Two nodes with the same value at different positions in the list are different nodes; a node whose next loops back to itself would show the same address twice, not the same value.

pos is documented as the zero-indexed tail connection point, but it is not passed to your function. Your function only sees head. This means you cannot rely on any cycle metadata — you must infer the cycle's existence purely from traversal behavior.

The empty list (n = 0) is in range. head will be None/null. That is not an edge case you need to special-case in a contrived way; it just falls out of whichever traversal you use.

Approach 1: hash set membership

The simplest reading of the problem: walk the list, keep a set of every node you have visited, and return true the moment you see a node that is already in the set.

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        visited = set()
        current = head
        while current is not None:
            if current in visited:
                return True
            visited.add(current)
            current = current.next
        return False

public class Solution {
    public bool HasCycle(ListNode head) {
        var visited = new HashSet<ListNode>();
        ListNode current = head;
        while (current != null) {
            if (visited.Contains(current)) return true;
            visited.Add(current);
            current = current.next;
        }
        return false;
    }
}

The set stores node references, not values. In Python that is object identity (id(current)); in C# the HashSet uses reference equality for class types by default. Two nodes that happen to have the same .val are still distinct objects and will not collide in the set.

Hand trace: [3, 2, 0, -4] with cycle at index 1

Let node addresses be A(3), B(2), C(0), D(-4), with D.next = B.

visited = {}
current = A  -> A not in visited -> add A -> current = B
visited = {A}
current = B  -> B not in visited -> add B -> current = C
visited = {A, B}
current = C  -> C not in visited -> add C -> current = D
visited = {A, B, C}
current = D  -> D not in visited -> add D -> current = B
visited = {A, B, C, D}
current = B  -> B IS in visited -> return True

Four steps to detect the cycle. In a list with no cycle, current eventually becomes None and the loop ends.

Complexity

Time: O(n). Each node is visited at most once before either a match fires or we fall off the end. Set lookup and insertion are O(1) amortized.

Space: O(n). In the worst case (no cycle, or the cycle closes at the very last step), we store every node in the set. That is the cost of this approach, and the follow-up is pointing directly at it.

Approach 2: Floyd's cycle detection — two pointers at different speeds

Floyd's algorithm (the "tortoise and hare") uses no extra storage. Two pointers start at head. slow advances one step per iteration; fast advances two. If there is a cycle, fast will eventually lap slow and they will meet inside the cycle. If there is no cycle, fast falls off the end first.

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

public class Solution {
    public bool HasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

The loop condition checks fast and fast.next before moving — you need both to be non-null because fast.next.next dereferences two levels deep. Checking only fast would give a null-pointer exception on the second dereference in a list of even length.

Why must they meet?

Suppose the list has a tail of length F before the cycle starts, and the cycle has length C. Once slow enters the cycle, fast is already somewhere inside it (it entered C/2 steps earlier and has been lapping). Define the gap as the distance fast is ahead of slow inside the cycle. Each step, fast moves two positions and slow moves one, so the gap shrinks by one per iteration (modulo C). Starting from some positive gap, the gap reaches zero — they meet — in at most C steps. The whole thing terminates in O(F + C) = O(n) time.

Hand trace: [3, 2, 0, -4] with cycle at index 1

Same nodes: A(3), B(2), C(0), D(-4), D.next = B.

slow = A, fast = A

Step 1: slow = B, fast = C   (fast skips to C=0 in 2 steps)
Step 2: slow = C, fast = B   (fast: C.next=D, D.next=B -> back to B)
Step 3: slow = D, fast = D   (fast: B.next=C, C.next=D -> D; slow: C.next=D -> D)
slow == fast -> return True

Three steps. The meeting point is at -4, node D. That is not necessarily the cycle entry point — to find the entry you would need LeetCode 142's extension.

Complexity

Time: O(n). The analysis above bounds it at O(F + C), and F + C <= n.

Space: O(1). Two pointer variables. Nothing else.

Edge cases that matter here

Empty list (head = None/null): The while fast and fast.next condition is immediately false. Return false. No special guard needed.

Single node, no self-loop ([1]): fast.next is null. Loop does not execute. Return false.

Single node with self-loop: fast.next is the node itself (not null), so the loop runs. On step 1, slow = node, fast = node. They meet immediately. Return true. This is the reason you check slow == fast inside the loop rather than initializing them at different positions.

Two nodes with cycle ([1, 2] where 2.next = 1): Step 1 moves slow to node 2 and fast (two steps) arrives back at node 1, then step 2 puts slow at 1 and fast at 1. Meet. Return true.

Long list, no cycle: fast reaches the tail in n/2 iterations. fast or fast.next becomes null, loop exits, return false. The constraint n <= 10^4 means this is fast.

Cycle closes at the very first node: F = 0. fast enters the cycle immediately. The distance gap argument still holds; they meet in at most C steps.

The comparison

Time complexity is the same. The difference is space. Hash set approach allocates memory proportional to the list length; Floyd's uses two local variables regardless of how large the list is.

Which one I'd ship

Floyd's, without hesitation. It is the canonical answer to the follow-up, it uses no extra memory, and the logic is only a few lines. The hash set approach is easier to explain to someone unfamiliar with the problem, but once you understand why the fast pointer must catch the slow one, the two-pointer solution is actually more elegant — you're using the cyclic structure of the problem to detect itself.

The hash set version has one advantage in interview settings: if you blank on Floyd's during a high-pressure whiteboard session, the set approach will pass all test cases and demonstrates you understood the problem. Ship the correct thing first, optimize if asked.

The underlying pattern here is fast-slow pointers, which is the standard tool for any question that asks you to detect or exploit periodicity in a sequence without storing the sequence. The idea that a pointer moving at 2x speed must eventually lap one at 1x speed in a finite cycle generalizes beyond linked lists — LeetCode 287 uses it on an array, LeetCode 202 uses it on a numeric sequence.

Where this sits in the linked-list series

This is the fourth article in the series, after Reverse Linked List (206), Merge Two Sorted Lists (21), and Reorder List (143). Those three problems are all about pointer manipulation within an acyclic list: reversing direction, merging two chains, reconnecting halves. Linked List Cycle introduces the detection question — something is wrong with the list's structure, and you need to find out if it is broken.

Linked List Cycle II (142) extends this directly: given that a cycle exists, find the node where the cycle begins. Floyd's algorithm gets you the meeting point; a second phase (reset one pointer to head, advance both at speed 1) gets you the entry. The math is elegant and worth working out.

Middle of the Linked List (876) uses the same fast-slow pointer mechanic: when fast reaches the end, slow is at the midpoint. Different problem, same structural intuition.

Find the Duplicate Number (287) reframes cycle detection entirely. An array of n+1 integers in [1, n] can be modeled as a linked list where index i points to value arr[i]. If there is a duplicate, that value is visited twice — which means there is a cycle. Floyd's algorithm finds the duplicate in O(1) space.

Happy Number (202) asks whether repeatedly replacing a number with the sum of squares of its digits eventually reaches 1. If the process cycles, it never reaches 1. Apply Floyd's on the sequence of numbers instead of list nodes. Same tool, wildly different surface.