Java Program to Detect Cycle in Linked List

Use Floyd's Cycle Detection algorithm in Java by moving two pointers, slow and fast, through the linked list; if they meet, a cycle exists. Example: boolean hasCycle(Node head) { Node slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; }

Examples

InputLinked list: 1 -> 2 -> 3 -> 4 -> 5 (no cycle)

Outputfalse

InputLinked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2)

Outputtrue

InputLinked list: empty (null head)

Outputfalse

How to Think About It

To detect a cycle in a linked list, use two pointers moving at different speeds: one moves one step at a time (slow), the other moves two steps at a time (fast). If the list has a cycle, these pointers will eventually meet inside the loop. If the fast pointer reaches the end (null), there is no cycle.

Algorithm

1

Start with two pointers, slow and fast, both at the head of the list.

2

Move slow pointer one step forward and fast pointer two steps forward in each iteration.

3

If at any point slow and fast point to the same node, return true (cycle detected).

4

If fast reaches the end of the list (null), return false (no cycle).

Code

java

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; this.next = null; }
}

public class CycleDetection {
    public static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        // Creating a cycle: 5 -> 2
        head.next.next.next.next.next = head.next;

        System.out.println(hasCycle(head)); // true
    }
}

Output

true

Dry Run

Let's trace the linked list with nodes 1->2->3->4->5 and a cycle from 5 back to 2 through the code.

1

Initialize pointers

slow = node 1, fast = node 1

2

First iteration

slow moves to node 2, fast moves to node 3

3

Second iteration

slow moves to node 3, fast moves to node 5

4

Third iteration

slow moves to node 4, fast moves to node 3 (due to cycle)

5

Fourth iteration

slow moves to node 5, fast moves to node 5

6

Pointers meet

slow == fast at node 5, cycle detected

Iteration	Slow Pointer	Fast Pointer
0	1	1
1	2	3
2	3	5
3	4	3
4	5	5

Why This Works

Step 1: Two pointers move at different speeds

The slow pointer moves one step, and the fast pointer moves two steps each time, allowing the fast pointer to catch up if a cycle exists.

Step 2: Pointers meet if cycle exists

If the linked list has a cycle, the fast pointer will eventually meet the slow pointer inside the loop, confirming the cycle.

Step 3: No cycle if fast pointer reaches end

If the fast pointer reaches null, it means the list ends and no cycle exists.

Alternative Approaches

Using HashSet to track visited nodes

java

import java.util.HashSet;

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; this.next = null; }
}

public class CycleDetection {
    public static boolean hasCycle(Node head) {
        HashSet<Node> visited = new HashSet<>();
        Node current = head;
        while (current != null) {
            if (visited.contains(current)) return true;
            visited.add(current);
            current = current.next;
        }
        return false;
    }
}

This method uses extra memory proportional to the number of nodes but is easy to understand.

Modifying node structure (not recommended)

java

class Node {
    int data;
    Node next;
    boolean visited = false;
    Node(int data) { this.data = data; this.next = null; }
}

public class CycleDetection {
    public static boolean hasCycle(Node head) {
        Node current = head;
        while (current != null) {
            if (current.visited) return true;
            current.visited = true;
            current = current.next;
        }
        return false;
    }
}

This approach modifies node data, which is unsafe and not recommended in practice.

Complexity: O(n) time, O(1) space

Time Complexity

The algorithm visits each node at most twice, so it runs in linear time, O(n), where n is the number of nodes.

Space Complexity

It uses only two pointers and no extra data structures, so space complexity is O(1).

Which Approach is Fastest?

Floyd's algorithm is faster and uses less memory than the HashSet method, which requires O(n) space.

Approach	Time	Space	Best For
Floyd's Cycle Detection	O(n)	O(1)	Memory efficient and fast detection
HashSet Tracking	O(n)	O(n)	Simple to implement but uses extra memory
Modifying Node	O(n)	O(1)	Unsafe, modifies data, not recommended