Detect Cycle in Linked List Floyd's Algorithm in DSA Python - Build from Scratch

Detect Cycle in Linked List using Floyd's Algorithm

📖 Scenario: Imagine you have a chain of connected train cars. Sometimes, the chain might loop back on itself, creating a cycle. We want to check if such a loop exists in our chain.

🎯 Goal: You will build a simple linked list and use Floyd's cycle detection algorithm to find out if the list has a cycle.

📋 What You'll Learn

Create a linked list with nodes containing integer values

Add a cycle by connecting the last node to one of the previous nodes

Implement Floyd's cycle detection algorithm using two pointers

Print True if a cycle is found, otherwise False

💡 Why This Matters

🌍 Real World

Detecting cycles in linked lists is important in computer memory management and network routing to avoid infinite loops.

💼 Career

Understanding cycle detection helps in debugging linked list problems and is a common interview question for software engineering roles.

1

Create a linked list with nodes

Create a class called Node with attributes value and next. Then create 5 nodes with values 1, 2, 3, 4, and 5. Link them so that node 1 points to node 2, node 2 points to node 3, node 3 points to node 4, and node 4 points to node 5. Store the first node in a variable called head.

DSA Python

# Your code here to create Node class and linked list with 5 nodes

Hint

Define a Node class with value and next. Then create nodes and link them one by one.

2

Create a cycle in the linked list

Create a cycle by setting the next of node5 to node3. This will make the list loop back from node 5 to node 3.

DSA Python

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

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

head = node1

# Create a cycle by linking node5.next to node3

Hint

Set node5.next equal to node3 to create the cycle.

3

Implement Floyd's cycle detection algorithm

Create two pointers called slow and fast and set both to head. Use a while loop that runs while fast and fast.next are not None. Inside the loop, move slow by one step (slow = slow.next) and fast by two steps (fast = fast.next.next). If at any point slow is equal to fast, set a variable has_cycle to True and break the loop. If the loop ends without finding a cycle, set has_cycle to False.

DSA Python

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

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

head = node1

node5.next = node3

# Implement Floyd's cycle detection algorithm below

Hint

Use two pointers moving at different speeds. If they meet, a cycle exists.

4

Print if the linked list has a cycle

Print the value of the variable has_cycle.

DSA Python

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

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

head = node1

node5.next = node3

slow = head
fast = head
has_cycle = False

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        has_cycle = True
        break

# Print the result below

Hint

Just print the has_cycle variable to see if a cycle was detected.

Practice

1. What is the main idea behind Floyd's Cycle Detection Algorithm in a linked list?

easy

A. Use two pointers moving at different speeds to detect a cycle

B. Count the number of nodes and check if it exceeds a limit

C. Reverse the linked list and check if it matches the original

D. Use a hash set to store visited nodes and check for repeats

Solution

1. Step 1: Understand Floyd's algorithm concept

   It uses two pointers, one moving fast (two steps) and one slow (one step).

2. Step 2: Detect cycle by pointer meeting

   If the fast pointer meets the slow pointer, a cycle exists in the linked list.

3. Final Answer:

   Use two pointers moving at different speeds to detect a cycle -> Option A

4. Quick Check:

   Two pointers at different speeds = cycle detection [OK]

Hint: Two pointers, slow and fast, meet if cycle exists [OK]

Common Mistakes:

• Thinking counting nodes detects cycle
• Assuming reversing list helps detect cycle
• Confusing hash set method with Floyd's algorithm

2. Which of the following is the correct way to move the fast pointer in Floyd's cycle detection?

easy

A. fast = fast.next

B. fast = fast.next.next

C. fast = fast.next.next.next

D. fast = fast.next.prev

Solution

1. Step 1: Understand fast pointer movement

   The fast pointer moves two steps at a time to catch up with the slow pointer.

2. Step 2: Identify correct syntax

   Moving two nodes ahead is done by fast = fast.next.next.

3. Final Answer:

   fast = fast.next.next -> Option B

4. Quick Check:

   Fast pointer moves two steps = fast.next.next [OK]

Hint: Fast pointer moves two nodes ahead using next.next [OK]

Common Mistakes:

• Moving fast pointer only one step
• Trying to move fast pointer three steps
• Using invalid pointer like prev in singly linked list

3. What will be the output of the following code snippet?

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = head.next  # cycle here

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

print(has_cycle(head))

medium

A. True

B. None

C. False

D. Error

Solution

1. Step 1: Analyze linked list structure

   Nodes 1->2->3 and then 3 points back to 2, creating a cycle.

2. Step 2: Trace Floyd's algorithm

   Slow and fast pointers will meet inside the cycle, so function returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Cycle exists, so output = True [OK]

Hint: Cycle means slow and fast pointers meet, so return True [OK]

Common Mistakes:

• Ignoring cycle creation line
• Assuming no cycle returns True
• Confusing None return with False

4. Find the error in the following Floyd's cycle detection code:

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

medium

A. No return statement for cycle detection

B. slow pointer moves two steps instead of one

C. Missing initialization of slow pointer

D. fast pointer moves only one step instead of two

Solution

1. Step 1: Check pointer movements

   Fast pointer should move two steps (fast = fast.next.next), but here it moves one step.

2. Step 2: Understand impact on cycle detection

   Moving one step slows fast pointer, so it may never meet slow pointer correctly.

3. Final Answer:

   fast pointer moves only one step instead of two -> Option D

4. Quick Check:

   Fast pointer must move two steps [OK]

Hint: Fast pointer must jump two nodes, not one [OK]

Common Mistakes:

• Moving fast pointer one step
• Confusing slow pointer movement
• Forgetting to check fast and fast.next

5. Given a linked list where the last node points back to the head (forming a cycle), how can Floyd's algorithm be adapted to find the node where the cycle begins?

hard

A. Use a hash set to store nodes and return the first repeated node

B. Count nodes until slow and fast meet, then return count as cycle start

C. After detecting cycle, reset slow to head and move both pointers one step until they meet

D. Reverse the linked list and check where reversal breaks

Solution

1. Step 1: Detect cycle using Floyd's algorithm

   Use slow and fast pointers to find meeting point inside cycle.

2. Step 2: Find cycle start node

   Reset slow to head, then move slow and fast one step at a time until they meet; meeting point is cycle start.

3. Final Answer:

   After detecting cycle, reset slow to head and move both pointers one step until they meet -> Option C

4. Quick Check:

   Reset slow and move both pointers one step to find cycle start [OK]

Hint: Reset slow to head, move both one step to find cycle start [OK]

Common Mistakes:

• Trying to count nodes to find cycle start
• Using reversal which doesn't help here
• Confusing hash set method with Floyd's approach