Linked List Cycle

Problem Summary

Given a linked list, return true if it has cycle else false

Key Observations

Solve it in $O (1)$ space complexity

Why This Works

(Explain the core reason the solution is correct.)

Example Scenario

Imagine two friends walking around a circular track:

One friend (the “slow” pointer) walks one lap per hour.
Another friend (the “fast” pointer) runs two laps per hour. If there is a cycle (the track is circular), the fast pointer will eventually “lap” or catch up to the slow pointer. This concept directly translates to data structures where pointers traverse nodes.

Main Concepts Used

(Mark the CS concepts or algorithms used.)

Fast & Slow Pointers

Time & Space Complexity

Time: $O (n)$ → Reason: Iterating through the linked list once
Space: $O (1)$ → Reason: Not storing a copy

Code

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

Common Mistakes / Things I Got Stuck On

Need to make sure slow and fast are not the same initially or move once before doing the if slow == fast check