Linked List Cycle (Hashing)

Given the head of a linked list, return true if following next pointers ever reaches the same node twice, meaning the list contains a cycle.

This is the hashing version of Detect a Cycle in a Linked List, which also covers Floyd's O(1)-space algorithm.

Example

Text

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

graph LR
    A["1"] --> B["2"] --> C["3"] --> D["4"]
    D --> B

Representing a list with a cycle

A Java node is an object, and next is a reference to another node object or null. Nodes are mutable, so the last node's next can point back to an earlier node, which creates a cycle. There are no wrapper types for "no next node": null means the list ends. Each node object has an identity, and HashSet<Node> uses it because Node does not override equals or hashCode.

Java

public class Main {
    static class Node {
        int val;
        Node next;

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

    // The last node points to the node at index pos, or to nothing when pos is -1. Returns the head.
    static Node build(int[] values, int pos) {
        Node[] nodes = new Node[values.length];
        for (int i = 0; i < values.length; i++) {
            nodes[i] = new Node(values[i]);
            if (i > 0) nodes[i - 1].next = nodes[i];
        }
        if (pos >= 0) nodes[values.length - 1].next = nodes[pos];
        return nodes[0];
    }

    public static void main(String[] args) {
        Node head = build(new int[]{1, 2, 3, 4}, 1);
        Node last = head.next.next.next;
        System.out.println("last node has value " + last.val + " and points to the node with value " + last.next.val);
    }
}

Output

last node has value 4 and points to the node with value 2

Brute force: has this node appeared earlier on the path?

At step s, the walk is at some node cur. Walk again from the head for s steps. If that walk passes through cur before step s, the list has come back to a node it visited earlier, which means a cycle.

Java

public class Main {
    static class Node {
        int val;
        Node next;

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

    static Node build(int[] values, int pos) {
        Node[] nodes = new Node[values.length];
        for (int i = 0; i < values.length; i++) {
            nodes[i] = new Node(values[i]);
            if (i > 0) nodes[i - 1].next = nodes[i];
        }
        if (pos >= 0) nodes[values.length - 1].next = nodes[pos];
        return nodes[0];
    }

    static boolean hasCycle(Node head) {
        Node cur = head;
        int steps = 0;
        while (cur != null) {
            Node probe = head;
            for (int s = 0; s < steps; s++) {
                if (probe == cur) {
                    return true; // cur was already visited earlier on the path
                }
                probe = probe.next;
            }
            cur = cur.next;
            steps++;
        }
        return false;
    }

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

Output

true false
first value: 1

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

Optimal: a HashSet of visited nodes

Walk the list once and insert each node into a set. add returns false for a node that is already there, which means the walk has come back to a visited node.

Walkthrough with the example:

The set holds node objects. The table names each node by its value, since the values here are distinct.

node	`add` returns	set after
1	true	{1}
2	true	{1, 2}
3	true	{1, 2, 3}
4	true	{1, 2, 3, 4}
2	false	cycle found

Java

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

public class Main {
    static class Node {
        int val;
        Node next;

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

    static Node build(int[] values, int pos) {
        Node[] nodes = new Node[values.length];
        for (int i = 0; i < values.length; i++) {
            nodes[i] = new Node(values[i]);
            if (i > 0) nodes[i - 1].next = nodes[i];
        }
        if (pos >= 0) nodes[values.length - 1].next = nodes[pos];
        return nodes[0];
    }

    static boolean hasCycle(Node head) {
        Set<Node> visited = new HashSet<>();
        Node cur = head;
        while (cur != null) {
            if (!visited.add(cur)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

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

Output

true false false
false first value: 1

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

Hash node identities, never values: [7, 7, 7] has three different nodes with the same value and no cycle. Hashing values would report a cycle that isn't there. This works because Node keeps the default equals and hashCode, which compare object identity. A Node that overrides them to compare val would break the check.

The same set also finds where the cycle starts: the first node for which add returns false is the first node of the cycle (the node with value 2 above).