Linked List Cycle

Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.

There is a cycle in a linked list if at least one node in the list can be visited again by following the next pointer.

Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it's next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.

Note: index is not given to you as a parameter.

There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Approach

Use Floyd's tortoise-and-hare algorithm. Move one pointer one step at a time and another pointer two steps at a time. If there is a cycle, they will eventually meet; if the fast pointer reaches the end, no cycle exists. This works for empty and single-node lists.

Why It Works

In a cyclic list, the fast pointer gains one node per step on the slow pointer, so it must eventually lap and meet it. In an acyclic list, the fast pointer reaches null first, proving there is no cycle.

Complexity

• Time: O(n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False