Vinay C.
Data Structures & Algorithms10 min read

Detect a cycle

Lesson 9.3 · Medium · Slow and fast · 10 min · by Vinay C

We'll cover the following

Decide whether a linked list loops back on itself, and find where the loop starts.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

16 items · 18 steps
slow/fast10
21
32
43
54
65
76
87
98
109
1110
1211
1312
1413
1514
1615

slow moves 1 step, fast moves 2. The tail of the list links back to node 6.

1 / 18

The idea

Complexity

TimeSpaceWhy
O(n)O(1)Inside a loop, fast gains one node per step, so they meet within one lap.

In Python

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast: return True
    return False
</> Now code it →Try it on LeetCode: Linked List Cycle II →

Summary: say it in the interview

  • Send a slow pointer (1 step) and a fast pointer (2 steps). In a loop the fast one laps the slow one and they must meet. With no loop, fast simply falls off the end. No extra memory is needed.
  • Time O(n), space O(1). Inside a loop, fast gains one node per step, so they meet within one lap.