Linked List Cycle: Fast and slow pointers Pattern

Learning Outcome

After this lesson, you should be able to explain why fast and slow pointers meet if a linked list contains a cycle.

Problem Statement

Given the head of a linked list, return true if the list has a cycle. A cycle means a node's next pointer points back to an earlier node.

Brute Force Approach

Store every visited node in a set. If the same node appears again, there is a cycle.

This is easy and correct, but it uses O(n) extra space.

Optimized Approach

Use Floyd's cycle detection. Move slow one step and fast two steps. If there is a cycle, fast eventually catches slow. If there is no cycle, fast reaches null.

Exact Pseudocode

slow = head
fast = head
while fast is not null and fast.next is not null:
  slow = slow.next
  fast = fast.next.next
  if slow == fast:
    return true
return false
  

Reference Code

class Solution:
    def hasCycle(self, head):
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True

        return False
  

Sample Dry Run

Complexity

Edge Cases

• Empty list.
• Single node with no cycle.
• Single node pointing to itself.

Interview Checklist

• Check fast and fast.next before moving two steps.
• Compare node references, not values.
• Explain why fast catches slow inside a cycle.

FAQs