Cycle Detection

Cycle Detection is a computer science concept related to graphs and linked lists. In graphs, a cycle is a path that starts and ends at the same vertex. In the context of linked lists, a cycle exists if traversing through the linked list leads to an infinite loop. Detecting cycles is crucial in many algorithms to prevent infinite loops or to understand the topology of the graph.

Solution

Here are code implementations for cycle detection in a singly linked list for Java, C++, and Python:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) return true;
        }

        return false;
    }
}

We use the “tortoise and hare” approach, where we have two pointers, one moving twice as fast as the other. If there’s a cycle, they will eventually meet.

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;

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

            if (slow == fast) return true;
        }

        return false;
    }
};

The logic remains the same as in the Java code, using two pointers at different speeds.

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

The Python implementation also follows the same logic, using two pointers.

The examples provided for cycle detection in the linked list are using Floyd’s Cycle Finding Algorithm, commonly known as the “Tortoise and the Hare” technique. In this algorithm, two pointers move through the list at different speeds. The slow pointer (tortoise) moves one step at a time, while the fast pointer (hare) moves two steps at a time.

If there is a cycle in the list, the fast pointer will eventually catch up to the slow pointer, and they will meet at some point within the cycle. If there’s no cycle, the fast pointer will reach the end of the list.

This algorithm is both efficient and easy to understand, making it a popular choice for cycle detection in linked lists.

Cycle detection has various applications, including garbage collection, network topology, and more. It helps in enhancing the efficiency of algorithms by early identification of loops and is an essential concept in data structure and algorithms.

Alternative Approaches

There are other ways to detect a cycle in a linked list or graph. Here are a couple of alternative methods:

  1. Using a Hash Set:

    • You can traverse the linked list and store each visited node’s reference (or address) in a hash set.
    • While traversing, if you find a node that is already in the hash set, it means there is a cycle.
    • If you reach the end of the linked list without finding any repeated references, there is no cycle.
    • This method requires additional space to store the references, so it’s not as space-efficient as Floyd’s algorithm.

  2. Modifying the Structure (not always applicable):

    • During the traversal, you can modify the current node’s reference to point to a specific “dummy” or “sentinel” node.
    • If during this process you encounter a node that already points to the dummy node, a cycle has been detected.
    • After the check, you’d typically need to restore the original structure, which might not always be feasible, depending on the use case and constraints.

  3. Using a Two-Pass Approach:

    • In the first pass, count the number of nodes in the list.
    • In the second pass, traverse the list again, but stop after the number of steps equal to the counted number of nodes.
    • If you have not reached the end of the list after that many steps, there is a cycle.
    • This method doesn’t require additional space but may not be as efficient as Floyd’s algorithm, especially if there’s a cycle close to the start of the list.

Each method has its trade-offs, and the choice might depend on specific constraints like available space, whether you can modify the structure, and the expected size and shape of the data.

title: Cycle Detection in a Graph excerpt: Cycle detection is the process of determining whether a grap contains a cycle. tags: cycle-detection

Cycle detection is the process of determining whether a graph contains a cycle. It is the process of checking whether a path through a graph returns to its beginning.

Cycle detection is easy if you think of the problem as one of topological sorting. A graph contains a cycle if and only if it cannot be topologically sorted. If you think of the graph as a topological sorting problem, the graph contains cycle if a series of tasks A, B, C, …, L forms a dependency loop.

After making this observation, detecting cycles is easy.

1
2
3
4
5
6
7
8
9

def cycle?
  # Try to topologically sort the graph
  
  if extend_partial_ordering.nil?
    return true
  end
  
  return false
end

This method returns true if the graph contains a cycle. Read about how to apply this concept to solve [Course Schedule]({% post_url 2021-01-10-course-schedule %}) problem.