# 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:

**Initialize Two Pointers**: Start with two pointers, slow (tortoise) and fast (hare), both set to the head of the list.**Move Pointers**: Move the slow pointer one step at a time and the fast pointer two steps at a time.**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.**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.