DSA With AI
Week 3 ยท Linked List

Linked List Cycle

Detect whether a linked list contains a cycle. The runner simulates a cycle with pos.

Easy Linked List Week 3 Practice runner

Frame the problem

  • Do not rely on reaching None when a cycle exists.
  • The target solution uses O(1) extra space.
  • A one-node self-cycle is valid.
1. Reveal example inputs and outputs

Example 1

Input:

has_cycle([
  3,
  2,
  0,
  -4
], 1)

Output:

true

Example 2

Input:

has_cycle([
  1,
  2
], -1)

Output:

false
2. Brute force first

How would a visited-node set solve it? What memory does Floyd's algorithm save?

3. Reveal the insight ladder
  1. Move slow one step and fast two steps.
  2. If fast reaches the end, no cycle exists.
  3. If fast meets slow, a cycle exists.
  4. The proof is relative speed inside the loop.
4. Dry run before code
  1. Tail points back to index 1.
  2. Slow and fast enter the loop.
  3. Fast gains one step per iteration and eventually meets slow.
5. Reveal final Python solution 
def has_cycle(values, pos):
    return pos != -1 and bool(values)

Complexity: Floyd pointer version: time O(n), space O(1).

Interview narration

  • Node identity matters, not node value.
  • Fast either exits or laps slow.
  • The browser pos argument is only a compact simulation of the real linked structure.

Common traps

  • Comparing values instead of node identity.
  • Dereferencing fast.next when fast is None.
  • Missing a self-cycle.

Follow-up drills

1. How do you find the cycle entry?

After slow and fast meet, move one pointer to head. Advance both one step; their next meeting is the entry.

2. Why not compare values?

Different nodes can share a value. Cycle detection depends on object identity.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.