Linked List: Detect a Cycle

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#include <iostream>
2#include <unordered_set>
3
4struct ListNode {
5    int val;
6    ListNode* next;
7    ListNode(int x) : val(x), next(nullptr) {}
8};
9
10bool hasCycle(ListNode* head) {
11    std::unordered_set<ListNode*> visited;
12    ListNode* current = head;
13    while (current != nullptr) {
14        if (visited.find(current) != visited.end()) {
15            return true;  // Cycle detected
16        }
17        visited.insert(current);
18        current = current->next;
19    }
20    return false;  // No cycle detected
21}
22
23int main() {
24    ListNode* head = new ListNode(1);
25    head->next = new ListNode(2);
26    head->next->next = new ListNode(3);
27    head->next->next->next = head->next;  // Creating a cycle for testing
28
29    std::cout << (hasCycle(head) ? "Cycle detected" : "No cycle detected") << std::endl;  // Output: Cycle detected
30
31    // Clean up memory (in a real scenario, you'd handle this more robustly)
32    delete head->next->next->next;  // This is part of the cycle, so must delete first
33    delete head->next->next;
34    delete head->next;
35    delete head;
36
37    return 0;
38}

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#include <iostream>
2
3struct ListNode {
4    int val;
5    ListNode* next;
6    ListNode(int x) : val(x), next(nullptr) {}
7};
8
9bool hasCycle(ListNode* head) {
10    if (!head || !head->next) {
11        return false;  // A single node or empty list can't have a cycle
12    }
13
14    ListNode* slow = head;
15    ListNode* fast = head;
16
17    while (fast && fast->next) {
18        slow = slow->next;  // Move slow pointer by one step
19        fast = fast->next->next;  // Move fast pointer by two steps
20
21        if (slow == fast) {
22            return true;  // Cycle detected
23        }
24    }
25
26    return false;  // No cycle detected
27}
28
29int main() {
30    ListNode* head = new ListNode(1);
31    head->next = new ListNode(2);
32    head->next->next = new ListNode(3);
33    head->next->next->next = head->next;  // Creating a cycle for testing
34
35    std::cout << (hasCycle(head) ? "Cycle detected" : "No cycle detected") << std::endl;  // Output: Cycle detected
36
37    // Clean up memory (in a real scenario, you'd handle this more robustly)
38    delete head->next->next->next;  // This is part of the cycle, so must delete first
39    delete head->next->next;
40    delete head->next;
41    delete head;
42
43    return 0;
44}

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.