Linked List Cycle#

Problem#

Given the head of a singly linked list, determine whether the list contains a cycle. A cycle exists if some node can be reached again by continuously following next pointers.

Example#

For 3 -> 2 -> 0 -> -4 where -4 points back to node 2, the answer is True. For a plain list 1 -> 2 that ends in None, the answer is False.

Brute force#

Store every visited node in a hash set. If you ever revisit a node, there is a cycle. This works but uses O(n) extra space.

Optimal approach#

Floyd’s tortoise and hare uses two pointers moving at different speeds. The slow pointer advances one node per step, the fast pointer two. If the list ends, the fast pointer reaches None and there is no cycle. If there is a cycle, the fast pointer eventually laps the slow pointer and they land on the same node. Meeting means a cycle exists. This needs only O(1) space.

Solution#

 1class ListNode:
 2    def __init__(self, val=0, next=None):
 3        self.val = val
 4        self.next = next
 5
 6
 7def has_cycle(head: ListNode | None) -> bool:
 8    slow = fast = head
 9    while fast and fast.next:
10        slow = slow.next
11        fast = fast.next.next
12        if slow is fast:
13            return True
14    return False
15
16
17a, b, c, d = ListNode(3), ListNode(2), ListNode(0), ListNode(-4)
18a.next, b.next, c.next, d.next = b, c, d, b  # d links back to b: cycle
19print(has_cycle(a))  # True
20
21x, y = ListNode(1), ListNode(2)
22x.next = y
23print(has_cycle(x))  # False

Complexity#

• Time: O(n), the pointers meet within one traversal.
• Space: O(1).

This is the classic fast and slow pointers problem. Keep going with the 60-day challenge.