Detect a Cycle in a Linked List

Understanding the Problem: Detecting a Cycle in a Linked List

A linked list is a linear data structure where each element (node) points to the next element in the sequence. However, in some cases, the last node might point back to one of the earlier nodes, creating a cycle (loop). The goal of this problem is to detect whether a cycle exists in the linked list.

Visualizing a Linked List without a Cycle:

Consider a normal linked list:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

Here, the list terminates when the last node (with value 5) points to NULL, indicating the end of the list.

Visualizing a Linked List with a Cycle:

Now, consider a linked list with a cycle:

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

In this case, the last node (with value 5) points back to node 3, creating a loop or cycle. This means that if you start traversing the list from node 1, you’ll keep cycling through nodes 3, 4, 5 indefinitely.

Challenges of Detecting a Cycle:

Without a cycle, traversing a linked list will always end when a node points to NULL.
With a cycle, you will never reach NULL. Instead, you’ll keep looping over a subset of the nodes repeatedly.

The challenge is to detect this cycle without using extra space or modifying the structure of the list. Using a brute-force approach, such as marking visited nodes, would require extra memory. Instead, we can use Floyd’s Cycle Detection Algorithm (Tortoise and Hare Algorithm), which is an efficient approach that only uses two pointers and operates in constant space.

Floyd’s Cycle Detection Algorithm (Tortoise and Hare)

The idea behind Floyd’s Cycle Detection is to use two pointers (slow and fast) to traverse the linked list:

Slow pointer (slow) moves one step at a time.
Fast pointer (fast) moves two steps at a time.

If there is no cycle, the fast pointer will eventually reach the end of the list (NULL). If there is a cycle, the fast pointer will eventually catch up to the slow pointer because it’s moving twice as fast.

Step-by-Step Explanation with Visuals

Step 1: Initial Setup

We start both the slow and fast pointers at the head of the list.

1 -> 2 -> 3 -> 4 -> 5
^
slow, fast

Both pointers start at node 1.

Step 2: Move the Pointers

Move slow by 1 step and fast by 2 steps:

code1 -> 2 -> 3 -> 4 -> 5
     ^     ^
    slow  fast

Move the pointers again:

code1 -> 2 -> 3 -> 4 -> 5
          ^           ^
         slow        fast

Step 3: Detect a Cycle

Keep moving slow and fast. If there is no cycle, fast will eventually reach the end (NULL).

However, if there is a cycle, at some point, slow and fast will meet within the cycle. For example:

rustCopy code1 -> 2 -> 3 -> 4 -> 5
        ^           |
        |___________|

Initially:

1 -> 2 -> 3 -> 4 -> 5
     ^     ^
    slow  fast

After several steps, they meet at node 4:

1 -> 2 -> 3 -> 4 -> 5
          ^     ^
         slow  fast

This meeting point confirms the presence of a cycle.

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the list. Both slow and fast traverse the list at most once.
Space Complexity: O(1) since no additional space is used beyond the two pointers.

C++ Solution:

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// Function to detect a cycle in a linked list using Floyd's Algorithm
bool hasCycle(Node* head) {
    if (!head || !head->next) return false;

    Node* slow = head;
    Node* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        // If slow and fast meet, a cycle exists
        if (slow == fast) return true;
    }

    return false;
}

// Utility function to create a cycle for testing
void createCycle(Node* head, int pos) {
    if (pos == -1) return;

    Node* tail = head;
    Node* cycleNode = nullptr;
    int index = 0;

    while (tail->next != nullptr) {
        if (index == pos) cycleNode = tail;
        tail = tail->next;
        index++;
    }
    tail->next = cycleNode;  // Creating a cycle
}

int main() {
    // Create a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
    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);
    head->next->next->next->next->next = new Node(6);

    createCycle(head, 2);  // Creating a cycle that connects node 6 to node 3

    if (hasCycle(head)) {
        cout << "Cycle detected in the list." << endl;
    } else {
        cout << "No cycle detected in the list." << endl;
    }

    return 0;
}

Java Solution:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;

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

            // If slow and fast meet, a cycle exists
            if (slow == fast) return true;
        }

        return false;  // No cycle
    }

    // Utility function to create a cycle for testing
    public void createCycle(ListNode head, int pos) {
        if (pos == -1) return;

        ListNode tail = head;
        ListNode cycleNode = null;
        int index = 0;

        while (tail.next != null) {
            if (index == pos) cycleNode = tail;
            tail = tail.next;
            index++;
        }
        tail.next = cycleNode;  // Creating a cycle
    }

    public static void main(String[] args) {
        LinkedListCycle solution = new LinkedListCycle();

        // Create linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);

        solution.createCycle(head, 2);  // Create a cycle at node 3

        if (solution.hasCycle(head)) {
            System.out.println("Cycle detected in the list.");
        } else {
            System.out.println("No cycle detected in the list.");
        }
    }
}

Python Solution:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    if not head or not head.next:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        # If slow and fast meet, there is a cycle
        if slow == fast:
            return True

    return False  # No cycle

# Utility function to create a cycle for testing
def createCycle(head, pos):
    if pos == -1:
        return

    tail = head
    cycleNode = None
    index = 0

    while tail.next:
        if index == pos:
            cycleNode = tail
        tail = tail.next
        index += 1

    tail.next = cycleNode  # Creating a cycle

# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)

createCycle(head, 2)  # Create a cycle connecting node 6 to node 3

if hasCycle(head):
    print("Cycle detected in the list.")
else:
    print("No cycle detected in the list.")