Detect a Cycle in Linked List

How to Detect a Cycle in a Linked List

A linked list is a basic data structure where each node connects to the next. In this blog, we will learn how to detect a cycle in a linked list. A cycle occurs when a node in the list links back to a previous node, creating a loop instead of ending with NULL. Detecting a cycle is important to avoid infinite loops and errors in programs.

We will use a simple and popular approach called the two-pointer technique, also known as the slow and fast pointer method. This method is easy to understand and works efficiently for cycle detection in linked lists.

Steps to Detect a Cycle in a Linked List

• Start with two pointers. Use a slow pointer and a fast pointer, both starting at the head of the linked list.
• Move the pointers. Move the slow pointer one step at a time and the fast pointer two steps at a time.
• Check if pointers meet. If the fast pointer and slow pointer meet at some point, there is a cycle in the linked list.
• Check the end of the list. If the fast pointer or its next node becomes NULL, the linked list does not have a cycle.
• Return the result. If the pointers meet, return true (cycle exists); otherwise, return false (no cycle).

Logic Building to Detect a Cycle in Linked List

Wonder if you're trapped in some kind of cycle where you're just repeating the same path over and over? Imagine playing a video game where your guy just runs around in a circle, ending up back where he started. How would you know that your guy's stuck in a cycle? Well, similar problem here: checking if a linked list has a cycle. Let's kick this off – sounds like a pretty interesting problem!

The video game challenge

Imagine a young developer named Sam who loves video games. One day, Sam got the following challenge: find out whether the linked list has a cycle—sort of detecting if some video game character is just running in an endless loop. Well, a cycle in a linked list simply indicates that there may be a node pointing back to the previous node that completes the circle. Ready to get cracking? Let's begin with the obvious.

The simple approach: Using a hash set

Sam’s first thought was to use a hash set to keep track of the nodes he had visited. If he encountered a node that was already in the hash set, it meant there was a cycle. This method is easy to understand and implement.

Steps Sam followed

• Traverse the List: How would you keep track of visited nodes? Use a hash set.
• Check for Cycle: What happens if you encounter a node that’s already in the hash set? It means there's a cycle.

Time and space complexity

• Time Complexity: O(n), where n is the number of elements in the linked list. Why? Because you need to traverse the list to check each node.
• Space Complexity: O(n), because you need extra space to store the nodes in the hash set.

C++ code example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <unordered_set>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    std::unordered_set<ListNode*> visited;
    ListNode* current = head;
    while (current != nullptr) {
        if (visited.find(current) != visited.end()) {
            return true;  // Cycle detected
        }
        visited.insert(current);
        current = current->next;
    }
    return false;  // No cycle detected
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = head->next;  // Creating a cycle for testing

    std::cout << (hasCycle(head) ? "Cycle detected" : "No cycle detected") << std::endl;  // Output: Cycle detected

    // Clean up memory (in a real scenario, you'd handle this more robustly)
    delete head->next->next->next;  // This is part of the cycle, so must delete first
    delete head->next->next;
    delete head->next;
    delete head;

    return 0;
}

Discovering a more efficient approach

Sam’s mentor, an experienced developer named Sarah, saw him working and suggested a more efficient way. She introduced Sam to Floyd’s Cycle-Finding Algorithm, also known as the Tortoise and Hare algorithm. This method uses two pointers moving at different speeds to detect a cycle.

The efficient approach: Floyd’s cycle-finding algorithm

Sarah explained that by using two pointers, one moving twice as fast as the other, they could determine if a cycle exists. If there’s a cycle, the two pointers will eventually meet. This method is efficient and doesn’t need extra space.

Steps Sarah followed

• Initialize Two Pointers: Can you think of how to use two pointers, slow and fast?
• Traverse the List: What if you move slow by one step and fast by two steps?
• Check for Meeting Point: If the two pointers meet, what does it mean? There is a cycle. If fast reaches the end, there is no cycle.

Time and space complexity

• Time Complexity: O(n), where n is the number of elements in the linked list. The pointers traverse the list.
• Space Complexity: O(1), because only a constant amount of extra space is used.

C++ code example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    if (!head || !head->next) {
        return false;  // A single node or empty list can't have a cycle
    }

    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;  // Move slow pointer by one step
        fast = fast->next->next;  // Move fast pointer by two steps

        if (slow == fast) {
            return true;  // Cycle detected
        }
    }

    return false;  // No cycle detected
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = head->next;  // Creating a cycle for testing

    std::cout << (hasCycle(head) ? "Cycle detected" : "No cycle detected") << std::endl;  // Output: Cycle detected

    // Clean up memory (in a real scenario, you'd handle this more robustly)
    delete head->next->next->next;  // This is part of the cycle, so must delete first
    delete head->next->next;
    delete head->next;
    delete head;

    return 0;
}

Conclusion

By comparing Sam’s simple approach with Sarah’s efficient Floyd’s Cycle-Finding Algorithm, we can see the importance of optimizing for space and time. The efficient method not only saves space but also works well with larger lists.