Learn�DSA�Linked Lists

Lesson 3 � Intermediate

Floyd's Cycle Detection (Tortoise-Hare)

Linked list mein cycle (loop) hona ek common problem hai. Interview mein ye question aata hai � linked list mein cycle hai ya nahi✓ Floyd's algorithm ye O(n) time aur O(1) space mein solve karta hai. Ye technique "tortoise and hare" kehlata hai � do pointers ek tez, ek slow.

? 20 min✓ Intermediate✓ Linked Lists Basics

Cycle problem kya hai?

WHAT

Cycle tab hota hai jab linked list ka koi node apne aap ko point kare directly ya indirectly. MATLAB last node ka next kisi previous node ko point kare � infinite loop ban jaata hai. Traverse karte waqt tum kabhi khatam nahi honge.

WHEN

Galti se cycle ban sakta hai jab insert/delete operations mein pointers galat set ho. Ya deliberately bhi banaya ja sakta hai � jaise circular linked list. Interview mein poochte hain ki tumhe detect karna hai ki cycle hai ya nahi, bina extra space use kiye.

WHERE

Detecting infinite loops, circular buffer management, detecting corruption in linked data structures, LRU cache implementation, DNS cache circular references.

Visualize karo: Imagine karo tum ek race track pe bhaag rahe ho. Agar track straight hai toh kabhi na kabhi finish line aa jayegi. But agar track circular hai toh tum ghoomte rehoge � kabhi khatam nahi hoga. Cycle wale linked list bhi aisa hi hota hai � ek circular track. 
# Cycle kaise banta hai � example
class Node:
 def __init__(self, data):
 self.data = data
 self.next = None

# Normal list: 1 ? 2 ? 3 ? 4 ✓ None
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)

# Cycle bana rahe hain: 4 ka next ? 2
head.next.next.next.next = head.next
# Ab: 1 ? 2 ? 3 ? 4 ? 2 ? 3 ? 4 ? 2 ? ... (infinite!)

# Traverse karo toh infinite loop!
# current = head
# while current: # Kabhi khatam nahi hoga!
# print(current.data)
# current = current.next

Floyd's Algorithm � Tortoise and Hare

Floyd's algorithm do pointers use karta hai � slow pointer (tortoise) jo ek step chalta hai, aur fast pointer (hare) jo do steps chalta hai. Agar cycle hai toh dono kabhi na kabhi milenge. Agar cycle nahi hai toh fast pointer end tak pahunch jayega.

# Floyd's Cycle Detection � O(n) time, O(1) space
def has_cycle(head):
 if head is None or head.next is None:
 return False
 
 slow = head # Tortoise � ek step
 fast = head # Hare � do steps
 
 while fast is not None and fast.next is not None:
 slow = slow.next # Ek step aage
 fast = fast.next.next # Do steps aage
 
 if slow == fast: # Mil gaye!
 return True
 
 return False # Fast end tak pahunch gaya � cycle nahi hai
Algorithm kyun kaam karta hai? Agar cycle hai toh fast pointer slow ko pakad lega � kyunki har step mein distance 1 kam hota hai. Jaise 100m race mein agar ek runner 2x speed se chale toh pakad lega. Mathematically: agar cycle length C hai, toh maximum C steps mein dono milenge.

Step-by-Step Visualization

Chalo dekhte hain kaise kaam karta hai. List hai: 1 ? 2 ? 3 ? 4 ? 5 ? 3 (cycle from 5 to 3)

# Step-by-step cycle detection
# List: 1 ? 2 ? 3 ? 4 ? 5 ? 3 (cycle)
#
# Step 0: slow=1, fast=1
# Step 1: slow=2, fast=3
# Step 2: slow=3, fast=5
# Step 3: slow=4, fast=4 ✓ MIL GAYE! Cycle detected!

# Another example: 1 ? 2 ? 3 ? 4 ? 2 (cycle from 4 to 2)
# Step 0: slow=1, fast=1
# Step 1: slow=2, fast=3
# Step 2: slow=3, fast=2
# Step 3: slow=4, fast=4 ✓ MIL GAYE!

# Agar cycle nahi hai: 1 ? 2 ? 3 ✓ None
# Step 0: slow=1, fast=1
# Step 1: slow=2, fast=3
# Step 2: slow=3, fast=None ✓ fast None hai, return False
Time Complexity: O(n) � agar cycle hai toh at most n steps mein mil jaayega. Agar cycle nahi hai toh fast pointer n/2 steps mein end tak pahunch jaata hai.

Space Complexity: O(1) � sirf do pointers use ho rahe hain, koi extra array nahi. Hash set approach O(n) space leti hai � isliye Floyd's better hai.

Cycle ka Starting Point kaise dhundho

Floyd's algorithm se pata chalta hai cycle hai ya nahi. But interview mein aksar poochte hain � cycle kahan se shuru hoti hai✓ Ye bhi O(n) time aur O(1) space mein solve ho sakta hai.

# Cycle ka starting point find karna
def detect_cycle_start(head):
 if head is None or head.next is None:
 return None
 
 slow = head
 fast = head
 
 # Pehle cycle detect karo
 while fast is not None and fast.next is not None:
 slow = slow.next
 fast = fast.next.next
 if slow == fast:
 break
 else:
 return None # Cycle nahi hai
 
 # Ab slow ko head pe wapas bhejo
 slow = head
 
 # Dono ek-ek step chalo � jahan milenge wo starting point hai
 while slow != fast:
 slow = slow.next
 fast = fast.next
 
 return slow # Ye cycle ka starting point hai
Mathematical Proof:
- Distance from head to cycle start = a
- Distance from cycle start to meeting point = b
- Cycle length = c
- Slow traveled: a + b
- Fast traveled: a + b + c (fast ne ek extra cycle complete ki)
- Fast = 2 � Slow ✓ a + b + c = 2(a + b) ✓ c = a + b ✓ a = c - b

Jab slow head pe wapas aata hai aur dono ek-ek step chalte hain, toh a steps mein milenge � exactly cycle start pe! 
# Find cycle start � step by step
# List: 1 ? 2 ? 3 ? 4 ? 5 ? 3 (cycle from 5 to 3)
# Cycle start = node with value 3
#
# Phase 1: Detect cycle
# slow and fast meet somewhere in cycle
#
# Phase 2: Reset slow to head
# slow = head (node 1)
# fast stays at meeting point
#
# Phase 3: Move both one step
# slow=1, fast=meeting ✓ slow=2, fast=? ✓ slow=3, fast=3
# They meet at node 3 = cycle start!

Try it: code khud likho




Exercise




Question: Function likho jo linked list mein cycle detect kare. Agar cycle hai toh "Yes", nahi toh "No" return karo. [1,2,3,4] mein cycle nahi hai � answer kya hoga?











Question: Agar linked list mein cycle hai toh cycle ki length kaise find karoge✓ Pseudocode likho. Answer mein length formula likho.









Common mistakes




Lesson complete?
Cycle detection samajh aa gaya✓ Ab merge sorted lists seekhte hain � ye merge sort algorithm ka fundamental building block hai.