Detect a Cycle in a Singly Linked List

Detecting a Cycle in a Singly Linked List

Detecting a cycle in a singly linked list involves determining if there is a loop where a node points back to one of the previous nodes. This can be efficiently achieved using Floyd's Cycle-Finding Algorithm, also known as the tortoise and hare algorithm.

---

Step-by-Step Process

Consider a singly linked list with a potential cycle:

Head -> 1 -> 2 -> 3 -> 4 -> 5
               ^              |
               |______________|

To detect a cycle in this list, follow these steps:

1. Initialize Two Pointers: Start with two pointers, slow (tortoise) and fast (hare), both set to the head of the list.
2. Move Pointers: Move the slow pointer one step at a time and the fast pointer two steps at a time.
3. Check for Cycle: If there is a cycle, the fast pointer will eventually meet the slow pointer within the cycle. If the fast pointer reaches the end of the list (i.e., None), there is no cycle.
4. Return Result: If the pointers meet, return True, indicating a cycle. If the fast pointer reaches the end, return False, indicating no cycle.

---

Python Program to Detect a Cycle in a Singly Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def create_cycle(self, pos):
        if pos == -1:
            return
        cycle_node = self.head
        last_node = self.head
        for _ in range(pos):
            cycle_node = cycle_node.next
        while last_node.next:
            last_node = last_node.next
        last_node.next = cycle_node

    def detect_cycle(self):
        slow = self.head
        fast = self.head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
linked_list.append(5)
linked_list.create_cycle(2)  # Create a cycle: 5 -> 3
print("Cycle detected:", linked_list.detect_cycle())  # Output: True

This Python program defines a singly linked list with methods for appending nodes, creating a cycle, detecting a cycle using Floyd's Cycle-Finding Algorithm, and traversing the list. The detect_cycle method returns True if a cycle is detected and False otherwise.