Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Additional information

• The number of nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

Example 1:

Input: head = [3, 2, 0, -4], pos = 1

Output: true

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

Example 2:

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

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

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

Output: false

Explanation: There is no cycle in the linked list.

Brute Force (Hash Set)

Intuition

We can traverse the list and store each visited node in a Hash Set. If we encounter a node already in the set, we have found a cycle. If we reach the end of the list, there is no cycle.

Algorithm

1. Initialize an empty set visited.
2. Traverse the list with curr = head.
3. For each node: if curr is in visited, return True. Otherwise, add curr to visited.
4. If curr becomes None, return False.

def has_cycle(head: Optional[ListNode]) -> bool:
    visited = set()
    curr = head
    while curr:
        if curr in visited:
            return True
        visited.add(curr)
        curr = curr.next
    return False

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit each node at most once.

• Space complexity: O(n)

• Reason: We store up to n nodes in the set.

Floyd's Cycle Detection (Optimal)

Intuition

We use two pointers moving at different speeds. The slow pointer moves one step at a time, the fast pointer moves two steps. If there is a cycle, the fast pointer will eventually catch up to the slow pointer inside the loop. If there is no cycle, the fast pointer will reach the end.

Algorithm

1. Initialize slow = head and fast = head.
2. While fast is not None and fast.next is not None:

• Move slow one step: slow = slow.next.
• Move fast two steps: fast = fast.next.next.
• If slow == fast, return True.

3. Return False.

def has_cycle(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

Time & Space Complexity

• Time complexity: O(n)

• Reason: If there is no cycle, the fast pointer reaches the end in O(n). If there is a cycle, the fast pointer catches the slow pointer within the cycle length.

• Space complexity: O(1)

• Reason: We only use two pointers.