15  Detect a Linked-List Cycle

Rank 13 · Pattern: Floyd’s fast and slow pointers · Target: \(O(n)\) time, \(O(1)\) space

15.1 Problem definition

Given the head of a singly linked structure, return whether repeatedly following next eventually revisits a node.

15.2 Clarifying questions

  1. Should I return only a boolean, or identify the cycle’s entry node as well?
  2. How should an empty list be classified?
  3. Is a cycle defined by revisiting the same node object or by encountering a repeated value?
  4. May I modify the nodes while checking them?

15.3 Sample answers

  1. Return only a boolean.
  2. An empty list has no cycle, so return false.
  3. Use node identity. Equal values in different nodes do not form a cycle.
  4. No. Leave every node and next reference unchanged.

15.4 Special data structure: ListNode

Values do not identify nodes: two separate nodes containing 4 are not a cycle.

The nested ListNode contains an int value and ListNode next, as in Chapter 14. Reference == checks identity.

ListNode has value and next attributes. The detector uses is, not ==, to compare node identity.

A cycle requires shared ownership, so links use Option<Rc<RefCell<ListNode>>>. The detector clones only a constant number of Rc handles, borrows links read-only, and uses Rc::ptr_eq for identity.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  N1["node 1"]
  N2["node 2: cycle entry"]
  N3["node 3"]
  N4["node 4"]

  N1 --> N2
  N2 --> N3
  N3 --> N4
  N4 --> N2

  classDef node fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class N1,N2,N3,N4 node;

15.5 Approach and invariant

Move slow one edge and fast two edges. If the list ends, fast or fast.next becomes null. If there is a cycle, both pointers eventually enter it, and the faster pointer gains one node per step around the loop until they meet.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  A["Set slow = head and fast = head"]
  B{"Do fast and fast.next exist?"}
  C["NO: return false; there is no cycle"]
  D["YES: move slow by 1 and fast by 2"]
  E{"Do slow and fast reference the same node?"}
  F["YES: return true; there is a cycle"]
  G["NO: continue the loop"]

  A --> B
  B --> C
  B --> D
  D --> E
  E --> F
  E --> G
  G --> B

  classDef plain fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class A,B,C,D,E,F,G plain;

Invariant: after \(t\) loop iterations, slow has followed \(t\) edges and fast has followed \(2t\) edges; neither pointer has been redirected or the list modified.

15.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class LinkedListCycleSolution {
    static class ListNode {
        int value;
        ListNode next;
        ListNode(int value) { this.value = value; }
    }

    static boolean 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;
    }

    @Test public void emptyListHasNoCycle() {
        assertFalse(hasCycle(null));
    }

    @Test public void singleTerminatedNodeHasNoCycle() {
        assertFalse(hasCycle(new ListNode(1)));
    }

    @Test public void twoTerminatedNodesHaveNoCycle() {
        ListNode first = new ListNode(1);
        first.next = new ListNode(2);
        assertFalse(hasCycle(first));
    }

    @Test public void detectsSelfCycle() {
        ListNode node = new ListNode(1);
        node.next = node;
        assertTrue(hasCycle(node));
    }

    @Test public void detectsCycleEnteringAtHead() {
        ListNode first = new ListNode(1);
        ListNode second = new ListNode(2);
        first.next = second;
        second.next = first;
        assertTrue(hasCycle(first));
    }

    @Test public void detectsCycleEnteringInMiddle() {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        a.next = b;
        b.next = c;
        c.next = b;
        assertTrue(hasCycle(a));
    }

    @Test public void repeatedValuesDoNotCreateCycle() {
        ListNode first = new ListNode(1);
        first.next = new ListNode(1);
        assertFalse(hasCycle(first));
    }

    @Test public void leavesLinksUnchanged() {
        ListNode first = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        first.next = second;
        second.next = third;

        hasCycle(first);

        assertSame(second, first.next);
        assertSame(third, second.next);
        assertNull(third.next);
    }

    public static void main(String[] args) {
        JUnitCore.main("LinkedListCycleSolution");
    }
}
import unittest


class ListNode:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def has_cycle(head):
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True

    return False


class LinkedListCycleTests(unittest.TestCase):
    def test_empty_list(self):
        self.assertFalse(has_cycle(None))

    def test_terminated_list(self):
        first = ListNode(1, ListNode(2))
        self.assertFalse(has_cycle(first))

    def test_detects_self_cycle(self):
        node = ListNode(1)
        node.next = node
        self.assertTrue(has_cycle(node))

    def test_detects_cycle_entering_at_head(self):
        first = ListNode(1)
        second = ListNode(2)
        first.next = second
        second.next = first
        self.assertTrue(has_cycle(first))

    def test_detects_cycle_entering_in_middle(self):
        first = ListNode(1)
        second = ListNode(2)
        third = ListNode(3)
        first.next = second
        second.next = third
        third.next = second
        self.assertTrue(has_cycle(first))

    def test_repeated_values_do_not_create_cycle(self):
        self.assertFalse(has_cycle(ListNode(1, ListNode(1))))

    def test_leaves_links_unchanged(self):
        first = ListNode(1)
        second = ListNode(2)
        third = ListNode(3)
        first.next = second
        second.next = third
        has_cycle(first)
        self.assertIs(second, first.next)
        self.assertIs(third, second.next)
        self.assertIsNone(third.next)


if __name__ == "__main__":
    unittest.main()
use std::cell::RefCell;
use std::rc::Rc;

pub type Link = Option<Rc<RefCell<ListNode>>>;

#[derive(Debug)]
pub struct ListNode {
    pub value: i32,
    pub next: Link,
}

impl ListNode {
    pub fn new(value: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self { value, next: None }))
    }
}

fn next(link: &Link) -> Link {
    link.as_ref().and_then(|node| node.borrow().next.clone())
}

pub fn has_cycle(head: &Link) -> bool {
    let mut slow = head.clone();
    let mut fast = head.clone();

    loop {
        slow = next(&slow);
        let fast_once = next(&fast);
        fast = next(&fast_once);

        match (&slow, &fast) {
            (Some(slow_node), Some(fast_node)) => {
                if Rc::ptr_eq(slow_node, fast_node) {
                    return true;
                }
            }
            _ => return false,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_list() {
        assert!(!has_cycle(&None));
    }

    #[test]
    fn terminated_list() {
        let first = ListNode::new(1);
        let second = ListNode::new(2);
        first.borrow_mut().next = Some(second);
        assert!(!has_cycle(&Some(first)));
    }

    #[test]
    fn detects_self_cycle() {
        let node = ListNode::new(1);
        node.borrow_mut().next = Some(node.clone());
        assert!(has_cycle(&Some(node)));
    }

    #[test]
    fn detects_cycle_entering_at_head() {
        let first = ListNode::new(1);
        let second = ListNode::new(2);
        first.borrow_mut().next = Some(second.clone());
        second.borrow_mut().next = Some(first.clone());
        assert!(has_cycle(&Some(first)));
    }

    #[test]
    fn detects_cycle_entering_in_middle() {
        let first = ListNode::new(1);
        let second = ListNode::new(2);
        let third = ListNode::new(3);
        first.borrow_mut().next = Some(second.clone());
        second.borrow_mut().next = Some(third.clone());
        third.borrow_mut().next = Some(second);
        assert!(has_cycle(&Some(first)));
    }

    #[test]
    fn repeated_values_do_not_create_cycle() {
        let first = ListNode::new(1);
        first.borrow_mut().next = Some(ListNode::new(1));
        assert!(!has_cycle(&Some(first)));
    }
}

The loop condition must check both fast and fast.next before evaluating fast.next.next.

15.7 High-value tests

Structure Expected Purpose
null false empty
one node → null false shortest acyclic
one node → itself true self-cycle
1 -> 2 -> null false even acyclic
tail points to middle true non-head cycle entry
repeated values, no repeated node false identity vs value

15.8 Complexity and correctness

Time is \(O(n)\) and space is \(O(1)\). In an acyclic list, fast reaches null after at most about \(n/2\) iterations. In a cyclic list, after both pointers enter a cycle of length \(c\), their relative distance changes by one modulo \(c\) per iteration, so it must become zero.

15.9 If the interviewer pushes

  • To return the cycle entry, first find the meeting point. Reset one pointer to head, move both one step at a time, and return where they meet.
  • To find cycle length, keep one pointer at the meeting point and count a full lap by the other.
  • A HashSet<ListNode> solution is often the clearest baseline and also identifies the first repeated node, but costs \(O(n)\) space.

15.10 TDD interview script

Confirm that only a boolean is required, cycles use node identity rather than value equality, empty input is acyclic, and the structure must not be modified. Then write this test list:

  1. Empty list
  2. One terminated node
  3. Two terminated nodes
  4. Self-cycle
  5. Cycle entering at the head
  6. Cycle entering in the middle
  7. Repeated values without a cycle
  8. Unchanged links

Run one red–green–refactor cycle per behavior. Linked structures need deliberately constructed identities; do not use value sequences to represent cyclic fixtures. After each increment, rerun the complete example and keep the detector free of marker writes or node mutation.

From book/src, run:

./java/run.sh LinkedListCycleSolution
./python/run.sh linked_list_cycle_solution
./rust/run.sh linked_list_cycle_solution

Narrate both termination arguments: in an acyclic list the fast pointer reaches null; in a cycle, the fast pointer gains one position per iteration relative to the slow pointer and must eventually meet it.

15.10.1 Pseudocode

slow = head
fast = head

while fast is not null and fast.next is not null:
    slow = slow.next
    fast = fast.next.next
    if slow and fast are the same node:
        return true

return false

After t iterations, slow has followed t edges and fast has followed 2t; comparisons and all list operations use node identity without changing links.

15.10.2 TDD sequence

Step Test code added Production code added or changed
1. Empty path emptyListHasNoCycle Initialize both pointers from head; the guarded loop skips and returns false.
2. One terminated node singleTerminatedNodeHasNoCycle Require both fast and fast.next before advancing two edges.
3. Even termination twoTerminatedNodesHaveNoCycle Advance slow by one and fast by two until the end without dereferencing null.
4. Smallest cycle detectsSelfCycle Compare the advanced pointers by identity and return true when they meet.
5. Cycle at head detectsCycleEnteringAtHead Repeat pointer movement; do not assume a self-loop or any acyclic prefix.
6. Cycle after prefix detectsCycleEnteringInMiddle Confirm both pointers eventually enter and meet inside a cycle whose entry is not the head.
7. Identity contract repeatedValuesDoNotCreateCycle Keep slow == fast identity comparison; never compare node values.
8. Read-only traversal leavesLinksUnchanged Confirm the algorithm only reads next and stores local references.

The progression covers both loop-guard boundaries and cycle shapes. Identity and non-mutation assertions prevent value-based or marking-based alternatives from silently changing the agreed contract.