LeetCode 141 - Linked List Cycle

Given the head of a singly-linked list, this Easy problem asks to determine if the list contains a cycle. Rather than storing visited node references in a hash set, I used Floyd’s cycle-finding algorithm with two pointers moving at different speeds to achieve O(1) auxiliary space.

---

Problem link and explanation

• Problem: 141. Linked List Cycle
• Summary: Given the head of a linked list, return True if there is a cycle where a node can be reached again by continuously following next pointers. Otherwise, return False.

While keeping a set of visited nodes takes O(n) space, the two-pointer approach leverages the property that within a cycle, a faster pointer will always catch up to a slower pointer one step at a time.

---

Approach

The slow pointer advances by one step per iteration while the fast pointer advances by two steps.

slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        return True

return False

1. Initialization: Start both pointers at head. If the list is empty or has only one node without a loop, return False immediately.
2. Traversal: Advance slow = slow.next and fast = fast.next.next while fast and fast.next are not None.
3. Collision check: If a cycle exists, the relative gap between fast and slow decreases by 1 on each iteration until slow == fast, confirming the cycle.
4. Termination: If fast reaches the end of the list (None), no cycle exists, and the function returns False.

---

Complexity analysis

• Time complexity: O(n)
  • If there is no cycle, fast reaches the end in n/2 steps. If a cycle exists, fast catches slow within at most one full cycle length after entering the loop.
• Space complexity: O(1)
  • Operates with only two pointer variables without allocating auxiliary data structures.

---

Implementation code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:

    def hasCycle(self, head) -> bool:
        if not head or not head.next:
            return False

        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

---

Summary and reflection

Floyd’s algorithm provides an elegant solution for cycle detection by converting a graph traversal problem into a relative speed collision check. Because the distance between the two pointers strictly decreases by 1 in each step inside the cycle, convergence is guaranteed without danger of an infinite loop.