Solving Linked List Cycle in Python: Step-by-Step Guide

Solving Linked List Cycle in Python: Step-by-Step Guide

The Linked List Cycle problem is one of the most classic algorithmic challenges you will encounter in coding interviews and real-world system design. It tests your understanding of pointers, memory references, and algorithmic optimization. In this tutorial, we will break down what a linked list cycle is, why it matters, and how to detect one efficiently in Python using multiple approaches.

What Is a Linked List Cycle?

A singly linked list is a sequence of nodes where each node contains a value and a reference (pointer) to the next node. Under normal circumstances, the last node points to None, marking the end of the list. A cycle occurs when a node's next pointer references an earlier node in the list, creating a loop that never terminates.

Visually, a cycled linked list looks like this:

1 -> 2 -> 3 -> 4 -> 5
              ^         |
              |_________|

In this example, node 5 points back to node 3, forming a cycle. If you try to traverse this list naively, your program will loop forever.

Why Detecting Cycles Matters

Detecting cycles is not just an academic exercise. In production systems, linked structures are used in memory allocators, LRU caches, graph representations, and event queues. An accidental cycle can cause infinite loops, memory leaks, or deadlocks. Detecting cycles early prevents catastrophic failures and is a fundamental skill for any backend or systems engineer.

From an interview perspective, this problem evaluates your ability to reason about time and space complexity, and whether you can move beyond brute-force solutions to elegant, optimal algorithms.

Defining the Node Structure

Before solving the problem, we need a basic node class. In Python, we typically use a simple class with two attributes: a value and a next pointer.

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

This structure allows us to chain nodes together. To create a list with a cycle for testing, we can manually link the nodes:

# Create nodes
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

# Link them: 1 -> 2 -> 3 -> 4 -> 5
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# Create cycle: 5 -> 3
node5.next = node3

Approach 1: Using a Hash Set

The most intuitive approach is to traverse the list while storing every visited node in a hash set. If we encounter a node that already exists in the set, a cycle exists. If we reach None, the list is acyclic.

def has_cycle_set(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next
    return False

This solution is correct and easy to understand. The time complexity is O(n) because we visit each node at most once. However, the space complexity is also O(n) because we store every node reference in the set. For large lists, this can be a significant memory burden.

Approach 2: Floyd's Tortoise and Hare Algorithm

The optimal solution uses two pointers moving at different speeds. The tortoise moves one step at a time, while the hare moves two steps at a time. If a cycle exists, the faster pointer will eventually lap the slower one and they will meet. If no cycle exists, the hare will reach None first.

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

This algorithm achieves O(n) time complexity and O(1) space complexity, making it the preferred solution in interviews and production code alike. The key insight is that within a cycle, the gap between the two pointers shrinks by one node on each iteration, guaranteeing they will eventually collide.

Why Floyd's Algorithm Works

Imagine the list has two parts: a linear segment of length k before the cycle begins, and a cycle of length c. Once both pointers enter the cycle, the hare gains one step on the tortoise per iteration. Since the cycle has c nodes, they will meet within at most c iterations. Therefore, the total work is bounded by O(n).

Approach 3: Finding the Cycle Start Node

Sometimes the problem extends beyond detection: you must also return the node where the cycle begins. Floyd's algorithm can be extended for this. Once the two pointers meet, reset one pointer to the head and move both one step at a time. The node where they meet again is the start of the cycle.

def detect_cycle_start(head):
    slow = head
    fast = head
    has_cycle = False

    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            has_cycle = True
            break

    if not has_cycle:
        return None

    # Phase 2: Find cycle start
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next

    return slow

The mathematical justification is elegant. If the cycle starts at index k and the pointers meet at position m inside the cycle, then moving one pointer back to the head and advancing both by one step means they will meet exactly at index k, the cycle entrance.

Approach 4: Modifying Node Values (Not Recommended)

Another approach involves marking visited nodes by changing their value to a sentinel, such as None or a special flag. While this uses O(1) extra space, it mutates the input data, which is generally unsafe and unacceptable in production systems.

def has_cycle_marking(head):
    while head:
        if head.val is None:
            return True
        head.val = None
        head = head.next
    return False

Avoid this approach unless the problem explicitly allows mutation and the original data is disposable.

Best Practices

• Prefer Floyd's algorithm for its optimal O(1) space complexity and clean implementation.
• Use identity checks (is) rather than equality (==) when comparing node references, since two distinct nodes may have equal values.
• Always handle edge cases such as an empty list (head is None) or a single node with no cycle.
• Avoid mutating input data unless explicitly permitted; side effects can introduce subtle bugs.
• Write unit tests covering acyclic lists, single-node cycles, full cycles, and long lists to validate your implementation.
• Document complexity in comments so future maintainers understand the trade-offs of each approach.

Testing the Implementation

A robust test suite ensures your solution handles all scenarios. Here is a simple test harness:

def test_has_cycle():
    # Test 1: No cycle
    a = ListNode(1)
    b = ListNode(2)
    a.next = b
    assert has_cycle_floyd(a) is False

    # Test 2: Single node with self-loop
    c = ListNode(1)
    c.next = c
    assert has_cycle_floyd(c) is True

    # Test 3: Cycle in the middle
    n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n4 = ListNode(4)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n2
    assert has_cycle_floyd(n1) is True
    assert detect_cycle_start(n1) is n2

    # Test 4: Empty list
    assert has_cycle_floyd(None) is False

    print("All tests passed.")

test_has_cycle()

Common Pitfalls

• Forgetting to check fast and fast.next before accessing fast.next.next, which causes AttributeError on short lists.
• Using == instead of is when comparing nodes, leading to false positives when values coincide.
• Assuming the cycle always starts at the head; cycles can begin at any node in the list.
• Returning a boolean when the problem asks for the cycle start node, or vice versa.

Conclusion

Detecting a cycle in a linked list is a foundational problem that bridges basic data structures and algorithmic thinking. While the hash set approach offers clarity and simplicity, Floyd's Tortoise and Hare algorithm stands out as the optimal solution with its constant space complexity and linear runtime. By understanding the mechanics behind pointer movement, the mathematical proof of cycle detection, and the extension to finding the cycle's starting node, you equip yourself with techniques that generalize to far more complex problems in graph traversal, memory management, and concurrency detection. Practice these implementations, test them against edge cases, and you will be well prepared to handle cycle detection confidently in both interviews and real-world codebases.