Skip to content
16-Week DSA Roadmap
LeetCode #141EasyProblem 6 of 8

Linked List Cycle

Decide whether a linked list loops back on itself, using a slow and a fast pointer (or a set of visited nodes).

  • Fast and slow pointers
  • Floyd's cycle detection

Before this, know: What a linked list is (see the week 4 overview), Hash sets (week 1)

The problem in plain English

You get head, the first node of a linked list. Normally the last node’s next is null, so walking the list eventually stops. But in a broken list, the last node may point back to an earlier node, forming a cycle (a loop): walking it would go round forever.

Return true if the list has a cycle, false if it doesn’t.

320-4
head = [3, 2, 0, -4] with pos = 1: the last node (-4) points back to node 2 (index 1). Starting at 3, a walk goes 3, 2, 0, -4, 2, 0, -4, 2, … forever.

How LeetCode describes the input: head = [3, 2, 0, -4], pos = 1. pos is the index the tail links back to (-1 means no cycle). Careful: your function never sees pos. It only gets head, and must discover the loop by walking.

The rules that matter:

  • The list can be empty, a single node, or a single node pointing to itself.
  • Values can repeat, so “I’ve seen this value before” proves nothing. Only “I’ve stood on this exact node before” does.
  • Follow-up: can you do it with O(1) memory?

Before you code: think it through

So: send two pointers down the list, slow moving 1 node per turn and fast moving 2. If fast ever reaches null, the list has an end: no cycle. If slow and fast ever land on the same node, there’s a loop.

Why must they meet? (Why can’t the hare jump over the tortoise?)

Once both are inside the loop, measure the gap: how many steps the hare is behind the tortoise, going round the loop. Each turn the tortoise moves 1 and the hare moves 2, so the hare gains exactly 1 step. The gap goes down by exactly 1 each turn: 3, 2, 1, 0. It can’t skip from 1 to −1, because it only ever shrinks by 1. When it hits 0 they’re on the same node.

THgap 3startTHgap 2after turn 1THgap 1after turn 2✓gap 0after turn 3they meet
A loop of 6 nodes. T = tortoise, H = hare. The hare starts 3 steps behind; after each turn the gap is one smaller, until they meet.

Pause and think

The loop has 5 nodes. The tortoise has just entered it, and the hare is 4 steps behind it. How many more turns until they meet? Could the tortoise go round the whole loop first?

Approach 1: Remember every node (hash set)

Walk the list and keep a hash set of the nodes we’ve stood on (a set stores items and answers “is this in here?” in about one step). If we ever arrive at a node that’s already in the set, we’ve gone round a loop. If we reach null, there’s no loop. The set stores nodes (their identity), not values, so repeated values don’t confuse it.

Hash set of visited nodes

head = [3, 2, 0, -4], pos = 1 (the tail links back to index 1)

320-4
variables
node
3node
result
—
seen (node #index (value))0 items

look up #0 (3): not found

    empty
  • Standing here now
  • In the set
  • Just added
  • Seen before: loop!

Is node #0 (3) in the set? No, first visit.

Step 1 / 9

Which line is running?

function hasCycle(head) {  const seen = new Set(); // the nodes we have already stood on  let node = head;  while (node !== null) {Running now:     if (seen.has(node)) return true; // been here before: we are going round a loop    seen.add(node);    node = node.next;  }  return false; // we fell off the end, so there is no loop}

Hash set of visited nodes

function hasCycle(head) {  const seen = new Set(); // the nodes we have already stood on  let node = head;  while (node !== null) {    if (seen.has(node)) return true; // been here before: we are going round a loop    seen.add(node);    node = node.next;  }  return false; // we fell off the end, so there is no loop}
def has_cycle(head):    seen = set()  # the nodes we have already stood on    node = head    while node is not None:        if node in seen:            return True  # been here before: we are going round a loop        seen.add(node)        node = node.next    return False  # we fell off the end, so there is no loop

What does it cost?

This one is actually fast: O(n) time, one visit per node. The problem is memory: the set grows to hold every node, O(n) extra space. For 10,000 nodes, 10,000 set entries. The follow-up asks for O(1) memory, and the hash set can’t do that.

The pattern: fast and slow pointers

This technique is called Floyd’s cycle detection, or “the tortoise and the hare”. Two pointers walk the same list at different speeds; how they end up tells you about the list’s shape (a loop, the middle, and more).

Pattern

Fast and slow pointers

Template

Use it when: you need to detect a loop, find the middle, or find where a cycle starts, with O(1) extra memory.

Signal words

  • “cycle”
  • “loop”
  • “middle of the linked list”
  • “O(1) memory”
  • “happy number”
  • “duplicate number”

Approach 2: Tortoise and hare

  1. Start slow and fast at head.
  2. While fast and fast.next both exist (so the hare can take 2 steps):
  3. Move slow one node and fast two nodes.
  4. If slow and fast are the same node, return true.
  5. If the loop ends, the hare found the end of the list: return false.

The shaded nodes form the loop (we can see it; the code can’t). Watch the gap in the variables panel once both pointers are in the loop. It’s measured at the end of each turn, after the hare moves (that’s when the code compares), and it drops by one every turn until it hits 0 and they meet. In the middle of a turn, after only the tortoise has moved, the panel still shows last turn’s gap. In the LeetCode example the tortoise even lands on the hare’s node mid-turn (turn 2): they share a node for a moment, but the code only compares after the hare moves, and by then the hare has moved on. Then try “No cycle”, where the hare runs off the end, and the edge cases.

Tortoise (slow) and hare (fast)

head = [3, 2, 0, -4], pos = 1 (the tail links back to index 1)

320-4
variables
slow
3node
fast
3node
turns
0
gap
—
result
—
  • Nodes in the loop
  • slow
  • fast
  • Where they meet

Both runners start at the head, node 3. slow (the tortoise) will move 1 node per turn, fast (the hare) 2 nodes per turn. The shaded nodes form the loop (we can see it; the code can't).

Step 1 / 10

Which line is running?

function hasCycle(head) {Running now:   let slow = head; // the tortoise  let fast = head; // the hare  while (fast !== null && fast.next !== null) {    slow = slow.next; // 1 step    fast = fast.next.next; // 2 steps    if (slow === fast) return true; // they met: there is a loop  }  return false; // the hare reached the end: no loop}

The code, line by line

Tortoise and hare

function hasCycle(head) {  let slow = head; // the tortoise  let fast = head; // the hare  while (fast !== null && fast.next !== null) {    slow = slow.next; // 1 step    fast = fast.next.next; // 2 steps    if (slow === fast) return true; // they met: there is a loop  }  return false; // the hare reached the end: no loop}
def has_cycle(head):    slow = head  # the tortoise    fast = head  # the hare    while fast is not None and fast.next is not None:        slow = slow.next  # 1 step        fast = fast.next.next  # 2 steps        if slow is fast:            return True  # they met: there is a loop    return False  # the hare reached the end: no loop

The line numbers match until line 7; Python then splits the return True onto its own line. On LeetCode the Python method is def hasCycle(self, head) in class Solution.

  • Lines 2–3: both runners start at the head.
  • Line 4: the hare is about to take two steps: fast.next, then fast.next.next. Both fast and fast.next must exist, or we’d read .next of null and crash. If either is missing, the list ends: no cycle.
  • Line 5: tortoise, one step. It never runs ahead of the hare, so if the hare got here safely, slow.next is safe too.
  • Line 6: hare, two steps.
  • Line 7: === (JS) / is (Python) compares identity: the same node object, not just equal values. Two different nodes that both hold 2 aren’t a meeting.
  • Line 9: the loop ended because the hare hit the end, so there’s no cycle.

We check for a meeting after moving, not before: at the start both are on the head, which would count as a meeting by mistake.

Dry run

head = [3, 2, 0, -4], pos = 1 (the loop is 2 → 0 → -4 → back to 2):

turnslowfastsame node?gap (hare behind)
start33(not checked)—
120no2
202no1
3-4-4yes → return true0
head = [3, 2, 0, -4], pos = 1

Each row is the state at the end of a turn, after the hare has moved. From turn 1 both are inside the loop (3 nodes long). The gap goes 2, 1, 0: one smaller every turn, exactly as promised.

Complexity

Hash set of nodes

Time

O(n)

Each node is visited once (plus one repeat visit if there's a loop).

Space

O(n)

The set ends up holding every node.

Tortoise and hare

Time

O(n)

Without a loop, the hare reaches the end in n/2 turns. With one, the tortoise enters the loop within n turns and is caught before finishing one lap.

Space

O(1)

Two pointers, whatever the list's length.

Common mistakes and edge cases

What to say out loud:

  1. “A hash set of visited nodes works in O(n) time but O(n) space.”
  2. “For O(1) space I’ll use a slow and a fast pointer.”
  3. “If there’s no loop, fast reaches null. If there is one, fast gains one step per turn, so the gap shrinks to zero and they meet.”
  4. “Compare node identity, and check fast and fast.next before jumping.”

Likely follow-ups:

  • “Where does the cycle start?” (Linked List Cycle II, LeetCode 142) After they meet, put one pointer back at the head and move both one step at a time; where they meet again is the start of the loop.
  • “How long is the loop?” After meeting, keep one pointer still and count steps until the other comes back round.

Related problems:

  • Find the Duplicate Number (LeetCode 287, week 5 of the roadmap): the same tortoise and hare, on an array treated as a linked list.
  • Reorder List: slow and fast pointers find the middle.
  • Happy Number (LeetCode 202): a “cycle” of numbers, detected the same way.