Linked List Cycle in Python — Floyd's Tortoise & Hare

Detecting a cycle in a linked list — LeetCode #141 — is one of the most iconic interview problems. There are two classic solutions: store visited nodes in a set for O(n) space, or use Floyd’s Tortoise-and-Hare algorithm to solve it in O(1) space.

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node in the list can be reached again by continuously following the next pointer.

Examples:

Input: head = [3,2,0,-4], pos = 1
Output: true  "Cycle formed by node at index 1 (value 2)"

Input: head = [1,2], pos = 0
Output: true

Input: head = [1], pos = -1
Output: false

The linked list: 3 → 2 → 0 → -4 → links back to index 1

Approach 1: Hash Set Tracking

Traverse the list, storing every visited node in a set. If a node reappears, a cycle exists.

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

def has_cycle_set(head):
    seen = set()
    current = head

    while current:
        if current in seen:
            return True
        seen.add(current)
        current = current.next

    return False

Time Complexity: O(n) — visits each node once Space Complexity: O(n) — set stores all nodes uniquely

Walkthrough

For head = [3, 2, 0, -4] with cycle at index 1:

Step 1: seen = {3},        current = 3 → OK
Step 2: seen = {3, 2},     current = 2 → OK
Step 3: seen = {3, 2, 0},  current = 0 → OK
Step 4: seen = {3, 2, 0, -4}, current = -4 → OK
Step 5: current = node at address of index 1 (value 2). It IS in seen.
        → Cycle detected ✅

Approach 2: Floyd’s Tortoise and Hare (Optimal)

Two pointers: slow moves one step, fast moves two steps. If they meet, there’s a cycle. If fast reaches None, no cycle.

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

def has_cycle_floyd(head):
    if not head or not head.next:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next        # tortoise moves 1 step
        fast = fast.next.next   # hare moves 2 steps

        if slow is fast:        # use `is` for identity comparison
            return True

    return False

Time Complexity: O(n) — fast catches slow in at most n iterations Space Complexity: O(1) — no extra storage!

Intuition

Imagine a circular track. A runner moving at 1x speed will eventually be caught by someone at 2x speed. If they never meet, the track isn’t circular.

Dry Run with Example

List: 1 → 2 → 3 → 4 → 5 → 3 (back to index 2)

Floyd’s algorithm steps:

Wait — why did slow=5 meet fast=5? Because fast lapped the cycle and caught up to slow once both were inside the cycle.

Verification with Assertions

def test_linked_list_cycle():
    # Case 1: No cycle
    head1 = ListNode(1)
    head1.next = ListNode(2)
    assert has_cycle_floyd(head1) == False

    # Case 2: One-node cycle (self-loop)
    head2 = ListNode(1)
    head2.next = head2
    assert has_cycle_floyd(head2) == True

    # Case 3: Multi-node cycle
    head3 = ListNode(3)
    n2 = ListNode(2)
    n0 = ListNode(0)
    n4 = ListNode(-4)
    head3.next = n2
    n2.next = n0
    n0.next = n4
    n4.next = n2  # cycle back to index 1
    assert has_cycle_floyd(head3) == True

    # Case 4: Empty list
    assert has_cycle_floyd(None) == False

    print("All tests passed!")

test_linked_list_cycle()

Follow-Up: Find Cycle Start (LeetCode #142)

Once a cycle is detected by Floyd’s algorithm, find the exact node where the cycle begins:

def detect_cycle_start(head):
    slow = fast = head

    # Phase 1: detect intersection
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break

    # No cycle
    if not fast or not fast.next:
        return None

    # Phase 2: reset slow to head, keep fast at intersection
    # Move both 1 step at a time until they meet at cycle start
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next

    return slow

Why this works: Let the meeting point be m steps from head. Then slow has traveled m and fast has traveled 2m. Since they met, 2m - m = m is a multiple of cycle length c. Now reset slow to head: after m more steps, both pointers arrive at the cycle start simultaneously.

Comparison

Common Mistakes

1. Using == instead of is — node identity matters, not value
2. Not handling None head — always check for null input
3. Advancing fast twice without check — fast.next might be None

Real-World Applications

• Detecting infinite recursion in compiled code
• Garbage collection reference loops
• Network routing table loops
• Chemical reaction cycles (e.g., detecting steady states)

Try the follow-up: modify the code to also count how many nodes are in the cycle.

Related Problems

• Linked List Cycle in Dart
• Linked List Cycle in Go
• Linked List Cycle in Swift
• Remove Duplicates from Sorted Array in Python
• Reverse Linked List in Python
• Move Zeroes in Python

FAQ

What is the best approach to solve Linked List Cycle in Python?

The recommended approach is the optimal approach, which runs in O(n) time with O(1) space. The full Python implementation is shown above.

What is the time complexity of Linked List Cycle in Python?

Using the optimal approach, the time complexity is O(n) and the space complexity is O(1).