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.