Two pointers walk a linked list at different speeds to detect cycles or find midpoints in O(N) time and O(1) memory.

Data Flow

        slow  fast
          |    |
   A -> B -> C -> D -> E
                       |       (cycle)
                       v
                       F -> G -> C

If there is a cycle, fast and slow MUST meet inside it.

When to use

• Detect a loop in a linked list.
• Find the middle of a linked list in one pass.
• Find the start of the cycle in O(1) extra memory.

How it works (cycle detection)

1. slow = fast = head
2. While fast and fast.next: slow = slow.next; fast = fast.next.next; if slow is fast -> there is a cycle.

How to find the cycle ENTRY

Once the two meet, reset one pointer to head and walk both at speed 1. They will meet at the cycle start node.

Code

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
 
def cycle_entry(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Pitfalls

• Forgetting the fast.next null-check before dereferencing.
• Not restarting from head after meeting — you’ll keep looping forever.

Analogy

Two runners on a circular track. The fast runner (2x speed) will lap the slow runner exactly at the cycle’s start if it exists.

Interview tip: If the problem is on a linked list and asks for constant extra space, try fast/slow first.