Navigating the Maze: Detecting Cycles in a Linked List with Python

Introduction

Hello, fellow coders! Today, we embark on a journey to tackle one of the intriguing challenges in linked list manipulation: detecting cycles. As a beginner, understanding how to check if a linked list has a cycle is a crucial skill that will sharpen your problem-solving abilities. In this blog post, we’ll explore the concept of cycles in linked lists, understand the algorithm to detect them, and implement the solution in Python with clear code examples.

The Mystery of Cycles in Linked Lists

In the realm of linked lists, a cycle occurs when a node in the list points back to a previous node, creating a loop. Detecting cycles is essential for preventing infinite loops and ensuring the proper functioning of algorithms that traverse linked lists.

Node Structure Reminder

Before we dive into the cycle detection algorithm, let’s revisit the structure of a node in a linked list:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next_node = None

Detecting Cycles

The algorithm to detect cycles in a linked list is based on the concept of slow and fast pointers. The idea is to have two pointers traverse the linked list at different speeds. If there is a cycle, the fast pointer will eventually catch up to the slow pointer.

def has_cycle(head):
    if not head or not head.next_node:
        return False  # No cycle if the list is empty or has only one node

    slow_pointer = head
    fast_pointer = head.next_node

    while fast_pointer and fast_pointer.next_node:
        if slow_pointer == fast_pointer:
            return True  # Cycle detected

        slow_pointer = slow_pointer.next_node
        fast_pointer = fast_pointer.next_node.next_node

    return False  # No cycle detected

Let’s visualize this with an example:

# Creating a linked list with a cycle: 1 -> 2 -> 3 -> 4 -> 2 (cycle)
linked_list_head = Node(1)
linked_list_head.next_node = Node(2)
linked_list_head.next_node.next_node = Node(3)
linked_list_head.next_node.next_node.next_node = Node(4)
linked_list_head.next_node.next_node.next_node.next_node = linked_list_head.next_node

# Checking for a cycle
has_cycle_result = has_cycle(linked_list_head)
print(f"Linked list has a cycle: {has_cycle_result}")