Leetcode 141 - Linked List Cycle

Problem

Leetcode 141. Linked List Cycle

Example:

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

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

Approach

We can use Floyd’s Tortoise and Hare algorithm to detect if there is a cycle in the linked list. We can have two pointers, slow and fast. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. If there is a cycle, the slow and fast pointer will eventually meet.

Visual representation of the approach:

list = 3 -> 2 -> 0 -> -4 -> 2 -> ...
slow = 3
fast = 3

slow moves 1 step forward:
slow = 2
fast moves 2 steps forward:
fast = 0

slow moves 1 step forward:
slow = 0
fast moves 2 steps forward:
fast = 2

slow moves 1 step forward:
slow = -4
fast moves 2 steps forward:
fast = 2

slow moves 1 step forward:
slow = 2
fast moves 2 steps forward:
fast = 2

slow == fast, so there is a cycle.

Here is the implementation of the approach:

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

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

            if slow == fast:
                return True

Time Complexity and Space Complexity

The time complexity is $ O(n) $ where $ n $ is the number of nodes in the linked list because we iterate through the linked list once.

The space complexity is $ O(1) $ because we are not using any extra space.