Problem Statement in English

You’re given a linked list node head. Your task is to return True if there is a cycle in the linked list, and False otherwise.

Approach

We build on a previous problem, 876. Middle Of Linked List, where we used the Fast and Slow Pointer Technique to find the middle of a linked list.

The important thing to note in this question is that we can only detect a cycle in the list if it exists. Which means, if there is no cycle, is that both pointers will reach the end of the list.

But if there is a loop, the slow pointer will eventually catch up to the fast pointer, as the fast pointer will be too busy going around the loop.

Solution in Python


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

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

            if fast == slow:
                return True

        return False

Complexity

  • Time: $O(n)$
    Since we iterate over atmost $n$ nodes in the linked list.

  • Space: $O(1)$
    Since we use 2 pointer variables.

And we are done.