How to Detect Cycle in Linked List in Python Easily

To detect a cycle in a linked list in Python, use Floyd's Cycle Detection algorithm, also called the tortoise and hare method. It uses two pointers moving at different speeds; if they meet, a cycle exists.

Syntax

The main idea is to use two pointers: slow and fast. Both start at the head of the linked list. slow moves one step at a time, while fast moves two steps. If fast meets slow at any point, there is a cycle.

• slow = slow.next: moves one node forward
• fast = fast.next.next: moves two nodes forward
• If fast or fast.next becomes None, the list has no cycle

python

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

Example

This example creates a linked list with a cycle and uses the has_cycle function to detect it. It prints True if a cycle exists, otherwise False.

python

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

# Create nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

# Link nodes
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # Creates a 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(node1))

Output

True

Common Pitfalls

Common mistakes include:

• Not checking if fast or fast.next is None before moving fast pointer, which causes errors.
• Using only one pointer, which cannot detect cycles efficiently.
• Modifying the linked list nodes accidentally during detection.

Always ensure to check pointers before advancing and avoid changing node links.

python

def wrong_has_cycle(head):
    slow = head
    fast = head
    while fast:
        slow = slow.next
        fast = fast.next.next  # This can cause AttributeError if fast.next is None
        if slow == fast:
            return True
    return False

# Correct way includes checking fast and fast.next

def correct_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

Quick Reference

• slow pointer: moves 1 step
• fast pointer: moves 2 steps
• cycle detected: when slow == fast
• no cycle: fast or fast.next becomes None

Key Takeaways

Use two pointers moving at different speeds to detect cycles efficiently.

Always check if pointers are None before advancing to avoid errors.

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

Do not modify the linked list nodes while detecting cycles.

Floyd's Cycle Detection algorithm is simple and runs in O(n) time with O(1) space.