Data Structures and Algorithms (DSA)  

Detect and Remove Cycle in a Linked List

Detect and Remove Cycle in a Linked List

📖 Introduction

A linked list is a widely used data structure in computer science. It is made up of nodes, where each node contains some data and a pointer (or reference) to the next node. Ideally, a linked list should end with null. However, sometimes due to programming mistakes or faulty pointer assignments, a cycle (or loop) may form.

A cycle in a linked list occurs when a node’s next pointer refers back to a previous node instead of pointing to null. This creates an endless loop, causing issues such as:

  • Infinite traversal while iterating through the list.

  • Memory leaks and performance problems.

  • Incorrect results in algorithms that depend on sequential traversal.

Detecting and removing cycles is a must-know skill in data structures and algorithms, especially for interviews and real-world programming.

🔎 What is a cycle in a linked list?

A cycle means the linked list does not terminate at null. Instead, the last node links back to one of the earlier nodes, creating a loop.

Example 1:

Input: 1 -> 3 -> 4 -> 3 (back to node 3)
Output: true

Here, node 4 connects back to node 3, forming a cycle.

Example 2:

Input: 1 -> 8 -> 3 -> 4 -> NULL
Output: false

In this case, the last node points to null, so no cycle exists.

🛠️ Approaches to detect a cycle

There are two popular ways to detect a cycle in a linked list:

✅ 1. Hashing Approach (Naive Method)

We use a HashSet to keep track of visited nodes.

  • Traverse the list node by node.

  • If a node is already present in the HashSet, it means the list has a cycle.

  • If traversal reaches null, there is no cycle.

Time Complexity: O(n)
Space Complexity: O(n)

Java Example using HashSet:

import java.util.HashSet;

class Node {
    int data;
    Node next;

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

class DetectCycleHashing {
    static boolean detectLoop(Node head) {
        HashSet<Node> visited = new HashSet<>();
        while (head != null) {
            if (visited.contains(head)) {
                return true; // Cycle found
            }
            visited.add(head);
            head = head.next;
        }
        return false; // No cycle
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(3);
        head.next.next = new Node(4);
        head.next.next.next = head.next; // Creates a cycle

        System.out.println(detectLoop(head)); // Output: true
    }
}

✅ 2. Floyd’s Cycle Detection Algorithm (Tortoise and Hare)

This is the most efficient method.

  • Use two pointers: a slow pointer (moves one step) and a fast pointer (moves two steps).

  • If the fast pointer reaches null, there is no cycle.

  • If the slow and fast pointers meet, a cycle exists.

Why does this work?
When both pointers enter the cycle, the fast pointer moves one step more than the slow in each iteration. Eventually, this step difference covers the full cycle length, causing them to meet at some node inside the cycle.

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

Java Example using Floyd’s Algorithm:

class Node {
    int data;
    Node next;

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

class DetectCycleFloyd {
    static boolean detectLoop(Node head) {
        Node slow = head, fast = head;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true; // Cycle found
            }
        }
        return false; // No cycle
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(3);
        head.next.next = new Node(4);
        head.next.next.next = head.next; // Creates a cycle

        System.out.println(detectLoop(head)); // Output: true
    }
}

🔧 How to remove a cycle

Once a cycle is detected using Floyd’s algorithm, we can also remove it:

  1. Keep one pointer at the head and the other at the meeting point.

  2. Move both pointers one step at a time.

  3. The point where they meet is the start of the cycle.

  4. To break the cycle, traverse the loop until you reach the node that points back to the start node. Set its next to null.

This will make the linked list linear again.

🛡️ Best Practices

  • Always check for empty lists before running detection.

  • Test edge cases:

    • Single node pointing to itself.

    • Two nodes pointing to each other.

    • Cycle starting at the head node.

  • Prefer Floyd’s Algorithm for cycle detection since it saves memory.

✅ Summary

A cycle in a linked list can cause infinite loops, memory leaks, and algorithm failures. To handle this:

  • Use the HashSet approach if simplicity is preferred.

  • Use Floyd’s Tortoise and Hare algorithm for an optimized solution.

  • After detection, always remove the cycle to restore normal list behavior.

Mastering linked list cycle detection and removal techniques is essential for programmers preparing for coding interviews and solving real-world problems in software development.

Membership not found