105 Linked List Cycle Detect if a cycle exists

 

Problem Statement

Given: The head of a singly linked list.
Goal: Determine whether there is a cycle in the list.

 What is a cycle?

A cycle exists when a node's next pointer refers back to a previous node instead of None.

Approach: Fast and Slow Pointers (Floyd's Algorithm)

Idea:

Use two pointers:

• Slow pointer moves one step at a time.

• Fast pointer moves two steps at a time.

If there is a cycle, the fast pointer will eventually meet the slow pointer.

If there is no cycle, the fast pointer will reach the end (None).

Why it works:

In a cycle, the fast pointer laps around the cycle and will eventually “catch” the slow pointer, similar to two runners on a circular track.

Time	O(n)	In worst case, fast traverses the list once
Space	O(1)	No extra space used

def hasCycle(head: ListNode) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps

        if slow == fast:
            return True           # cycle detected

    return False                  # no cycle

Why "eventually"?

Because:

• They do not meet immediately.

• The fast pointer is moving 2 steps at a time, slow is moving 1 step at a time.

• The distance between them changes over time, and they gradually close the gap.

• It may take multiple iterations before they land on the same node.