How to Detect Cycle in Linked List: Simple Methods Explained

To detect a cycle in a linked list, use two pointers called slow and fast. Move slow by one step and fast by two steps; if they meet, a cycle exists. If fast reaches the end, the list has no cycle.

Syntax

The common method to detect a cycle uses two pointers:

• slow: moves one node at a time
• fast: moves two nodes at a time

If fast or fast.next becomes null, the list ends with no cycle. If slow equals fast at any point, a cycle is detected.

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 detection function to confirm the cycle's presence.

python

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

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

# 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

# Detect cycle
print(has_cycle(node1))

Output

True

Common Pitfalls

Common mistakes when detecting cycles include:

• Not checking if fast or fast.next is null before moving pointers, which causes errors.
• Using only one pointer, which cannot detect cycles reliably.
• Confusing node values with node references; cycle detection depends on node identity, not values.

python

def wrong_has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:  # Fixed missing check for fast being None
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Correct way includes checking both 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

• Use two pointers: slow moves 1 step, fast moves 2 steps.
• If fast or fast.next is null, no cycle exists.
• If slow meets fast, a cycle is detected.
• Always check pointer validity before moving to avoid errors.

Key Takeaways

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

Always check that pointers are not null before advancing them.

Meeting of slow and fast pointers confirms a cycle in the linked list.

Single pointer traversal cannot reliably detect cycles.

Cycle detection depends on node references, not node values.