Skip to content
LEETFLIX

Linked List Cycle

EasyHashingLinked listTwo pointers
Solve on LeetCode

Easy · Floyd cycle detect. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 141. Linked List Cycle. The copyrighted prompt is on LeetCode. This page is a working Floyd cycle detect for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

head =
[3, 2, 0, -4]
pos =
1

Output

true

The tail links back to index 1, so the walk loops.

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Floyd: slow + fast

pos is the index the tail links back to (−1 = acyclic). Slow walks one step, fast walks two. If they meet, there is a cycle.

On a cycle the fast pointer laps the slow one. On a line it hits the end first. No extra set of visited nodes.

Algorithm

  1. If pos < 0 or the list is empty, return false.
  2. Advance slow by 1 and fast by 2 (wrapping the tail to pos).
  3. If they land on the same index, return true.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def hasCycle(self, head: list[int], pos: int) -> bool:        n = len(head)        if n == 0 or pos < 0:            return False        def nxt(i: int) -> int:            return pos if i == n - 1 else i + 1        slow = fast = 0        while True:            slow = nxt(slow)            fast = nxt(nxt(fast))            if slow == fast:                return True
Watch this run

03

Interactive walkthrough

Playing “Floyd: slow + fast”. Edit the input, hit Run, then scrub.

Approach: Floyd: slow + fast

Loading animation…