Detect a Cycle in a Linked List

Given the head of a linked list, return true if the list has a cycle: following next pointers eventually leads back to a node that was already visited. Otherwise return false.

LeetCode: 141. Linked List Cycle

Example 1

Text

Input:  3 -> 2 -> 0 -> -4, and -4 points back to 2
Output: true

graph LR
    A["3 (index 0)"] --> B["2 (index 1)"] --> C["0 (index 2)"] --> D["-4 (index 3)"]
    D --> B

Example 2

Text

Input:  1 -> 2 -> 3 -> null
Output: false

Building a list with a cycle

In Java, next is a reference to a node object, and null marks the end of the list. Assigning the last node's next to an earlier node creates a cycle. The build helper below keeps every node in an array so the examples can name a node by its index, and points the last node at index pos.

Java

public class Main {
    static class Node {
        int val;
        Node next; // null marks the end of the list

        Node(int val) {
            this.val = val;
        }
    }

    // Builds a list from values; the last node points to index pos (or to null when pos is -1).
    static Node[] build(int[] values, int pos) {
        int n = values.length;
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(values[i]);
        }
        for (int i = 0; i + 1 < n; i++) {
            nodes[i].next = nodes[i + 1];
        }
        if (pos >= 0) nodes[n - 1].next = nodes[pos];
        return nodes;
    }

    public static void main(String[] args) {
        Node[] list = build(new int[]{3, 2, 0, -4}, 1);
        for (int i = 0; i < list.length; i++) {
            Node next = list[i].next;
            System.out.println("index " + i + ": val " + list[i].val + ", next val " + (next == null ? "none" : next.val));
        }
    }
}

Output

index 0: val 3, next val 2
index 1: val 2, next val 0
index 2: val 0, next val -4
index 3: val -4, next val 2

Brute force: remember every node you've visited

Walk the list and store each node in a HashSet. If we reach a node that's already in the set, we've gone around a cycle. If we reach null, there's no cycle.

Walkthrough with example 1:

current index	in set?	set after
0	no	{0}
1	no	{0, 1}
2	no	{0, 1, 2}
3	no	{0, 1, 2, 3}
1	yes, return true

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static class Node {
        int val;
        Node next; // null marks the end of the list

        Node(int val) {
            this.val = val;
        }
    }

    // Builds a list from values; the last node points to index pos (or to null when pos is -1).
    static Node[] build(int[] values, int pos) {
        int n = values.length;
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(values[i]);
        }
        for (int i = 0; i + 1 < n; i++) {
            nodes[i].next = nodes[i + 1];
        }
        if (pos >= 0) nodes[n - 1].next = nodes[pos];
        return nodes;
    }

    static boolean hasCycle(Node head) {
        Set<Node> seen = new HashSet<>(); // Node does not override equals, so the set compares identity
        for (Node cur = head; cur != null; cur = cur.next) {
            if (!seen.add(cur)) {
                return true; // visited before
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Node[] looped = build(new int[]{3, 2, 0, -4}, 1);
        Node[] straight = build(new int[]{1, 2, 3}, -1);
        System.out.println(hasCycle(looped[0]) + " " + hasCycle(straight[0]));
    }
}

Output

true false

Time: O(n). Space: O(n) for the set.

Store the nodes, not their values. Two different nodes can hold the same value without forming a cycle. Node does not override equals or hashCode, so the set compares object identity. A node class that compared by value would report a cycle for any repeated value.

Optimal: Floyd's fast and slow pointers

Move slow one node at a time and fast two nodes at a time.

If there's no cycle, fast reaches the end.
If there's a cycle, both pointers end up inside it. Each step, fast gains one node on slow, so the gap between them shrinks by one per step until they land on the same node. That takes at most one trip around the cycle.

Walkthrough with example 1 (indexes shown):

step	slow	fast
start	0	0
1	1	2
2	2	1 (3 → back to 1)
3	3	3 (1 → 2 → 3)

They meet at index 3, so there's a cycle.

Java

public class Main {
    static class Node {
        int val;
        Node next; // null marks the end of the list

        Node(int val) {
            this.val = val;
        }
    }

    // Builds a list from values; the last node points to index pos (or to null when pos is -1).
    static Node[] build(int[] values, int pos) {
        int n = values.length;
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(values[i]);
        }
        for (int i = 0; i + 1 < n; i++) {
            nodes[i].next = nodes[i + 1];
        }
        if (pos >= 0) nodes[n - 1].next = nodes[pos];
        return nodes;
    }

    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) { // fast falls off the end when there is no cycle
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;          // they met
        }
        return false;
    }

    public static void main(String[] args) {
        Node[] looped = build(new int[]{3, 2, 0, -4}, 1);
        Node[] straight = build(new int[]{1, 2, 3}, -1);
        Node[] selfLoop = build(new int[]{1}, 0);
        System.out.println(hasCycle(looped[0]) + " " + hasCycle(straight[0]) + " " + hasCycle(selfLoop[0]));
        System.out.println(hasCycle(null));
    }
}

Output

true false true
false

Time: O(n). Space: O(1).

The condition fast != null && fast.next != null is checked before fast.next.next is read, so fast can stop after one or two moves without a NullPointerException. An empty list (null head) skips the loop and returns false.

Follow-up: where does the cycle start?

(LeetCode 142.) After the pointers meet, move one pointer back to the head and advance both one node at a time. They meet again at the first node of the cycle:

Java

public class Main {
    static class Node {
        int val;
        Node next; // null marks the end of the list

        Node(int val) {
            this.val = val;
        }
    }

    // Builds a list from values; the last node points to index pos (or to null when pos is -1).
    static Node[] build(int[] values, int pos) {
        int n = values.length;
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(values[i]);
        }
        for (int i = 0; i + 1 < n; i++) {
            nodes[i].next = nodes[i + 1];
        }
        if (pos >= 0) nodes[n - 1].next = nodes[pos];
        return nodes;
    }

    static Node cycleStart(Node head) {
        Node slow = head, fast = head;
        while (true) {
            if (fast == null || fast.next == null) return null; // no cycle
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        Node a = head;
        while (a != slow) {
            a = a.next;
            slow = slow.next;
        }
        return a;
    }

    public static void main(String[] args) {
        Node[] nodes = build(new int[]{0, 1, 2, 3}, 1); // the values equal the indexes
        Node start = cycleStart(nodes[0]);
        System.out.println(start == null ? "none" : "index " + start.val);
        System.out.println(cycleStart(build(new int[]{0, 1, 2}, -1)[0]));
    }
}

Output

index 1
null

This works because the distance from the head to the cycle's start equals the distance from the meeting point to the cycle's start, measured forward around the cycle. The second call shows the result for a list without a cycle (null).

Cycles and memory

The garbage collector reclaims objects that are unreachable from the running program, including a cycle that nothing points to from outside. A list with a cycle therefore needs no special cleanup. Use == to compare nodes by identity.