Linked List Cycle

The problem description can be found in LeetCode.

Approach

There are several ways to solve this problem and, as usual, we have to clarify the requirements with the interviewer.

1. Iterate over the Linked List and add the node value to a Set. If the value is already in the set, then it means that there is a cycle. This would require $O(n)$ time and $O(n)$ space. However, this would assume that no value is duplicated unless the cycle is present.
2. Another technique consists of applying the Floyd's tortoise and hare algorithm. We would keep two pointers: one moves by one step and one moves by two steps. If there is a cycle, the two pointers will meet at some point.

Solution

from typing import Optional


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head.next if head else None

        while fast and fast.next:
            if slow == fast:
                return True

            slow = slow.next
            fast = fast.next.next

        return False

Complexity

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

Where $n$ is the size of the linked list.