Detect cycle in linked list

In this tutorial, we will see Java program to detect a cycle in a linked list

• The LinkedList class defines a Node inner class that represents a node in the linked list.
• The detectCycle method takes a Node as input and returns true if the linked list contains a cycle, or false otherwise.
• The method uses two pointers, a slow pointer and a fast pointer, to traverse the list.
• The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.
• If the linked list contains a cycle, the fast pointer will eventually catch up to the slow pointer, at which point the method returns true.
• If the fast pointer reaches the end of the list without catching up to the slow pointer, the method returns false.

import java.util.*;

class LinkedList {
    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    static boolean detectCycle(Node head) {
        if (head == null || head.next == null) {
            // The list is empty or has only one node, so it cannot contain a cycle
            return false;
        }

        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // Check if the fast pointer has caught up to the slow pointer
            if (slow == fast) {
                // A cycle has been detected
                return true;
            }
        }

        // No cycle was found
        return false;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        // Create a linked list with a cycle
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3;

        // Check if the linked list contains a cycle
        boolean hasCycle = detectCycle(head);

        if (hasCycle) {
            System.out.println("The linked list contains a cycle");
        } else {
            System.out.println("The linked list does not contain a cycle");
        }
    }
}

Initial state:

1 -> 2 -> 3 -> 4 -> 5 -> null
^                        |
--------------------------

The slow pointer is at node 1, and the fast pointer is at node 1.

First iteration:

1 -> 2 -> 3 -> 4 -> 5 -> null
     ^              |
     ----------------

The slow pointer is at node 2, and the fast pointer is at node 3.

Second iteration:

1 -> 2 -> 3 -> 4 -> 5 -> null
               ^    |
               ------

The slow pointer is at node 3, and the fast pointer is at node 5.

Third iteration:

1 -> 2 -> 3 -> 4 -> 5 -> null
                    ^ |
----------------------

The slow pointer is at node 4, and the fast pointer is at node 3.

A cycle has been detected, so the method returns true.

Thanks for reading…