Easy#1416 min readLinked ListsTwo PointersLeetCode

Linked List Cycle

Floyd's tortoise and hare

Floyd’s tortoise and hare. Understand WHY fast catches slow.

Published Apr 15, 2026

The full write-up: intuition, approaches, traces and solutions.

Problem

Given the head of a linked list, determine whether the list contains a cycle.

In LeetCode terms, the list may contain a node whose next pointer points back to a previous node. The node values themselves do not matter. You are reasoning about identity, not equality.

Input

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

Output

true

Explanation

The tail connects back to the node with value 2.

Input

head = [1,2], pos = 0

Output

true

Input

head = [1], pos = -1

Output

false

Intuition

There are two standard ways to detect a cycle:

remember every node you have seen
move one pointer twice as fast as the other

The second one is the important one. If there is no cycle, the fast pointer eventually falls off the list. If there is a cycle, the fast pointer gains one node of relative distance on the slow pointer every step, so it must eventually lap it.

That is the whole proof. The cycle is a closed loop, and the relative speed is nonzero. Meeting is inevitable.

Approach

Seen Nodes

TimeO(n)

SpaceO(n)

Store every visited node in a set keyed by node identity. If you ever encounter the same node again, there is a cycle.

This is the most direct implementation, and it is useful as a correctness baseline, but it spends extra memory on a problem that does not need it.

use std::collections::HashSet;

impl Solution {
    pub fn has_cycle(head: Option<Box<ListNode>>) -> bool {
        let mut seen: HashSet<*const ListNode> = HashSet::new();
        let mut curr = head.as_deref();

        while let Some(node) = curr {
            let ptr = node as *const ListNode;
            if !seen.insert(ptr) {
                return true;
            }
            curr = node.next.as_deref();
        }

        false
    }
}

Rust · runnable

function hasCycle(head: ListNode | null): boolean {
  const seen = new Set<ListNode>();
  let curr = head;

  while (curr !== null) {
    if (seen.has(curr)) return true;
    seen.add(curr);
    curr = curr.next;
  }

  return false;
}

TypeScript · runnable

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen: set[ListNode] = set()
        curr = head

        while curr is not None:
            if curr in seen:
                return True
            seen.add(curr)
            curr = curr.next

        return False

Python · runnable

Floyd's Tortoise and Hare

TimeO(n)

SpaceO(1)

Recommended

Move slow one step at a time and fast two steps at a time. If fast reaches the end, there is no cycle. If slow and fast ever point to the same node, the pointers are inside the cycle and the list is cyclic.

The proof is a relative-speed argument, not a value comparison. That distinction matters.

impl Solution {
    pub fn has_cycle(head: Option<Box<ListNode>>) -> bool {
        let mut slow = head.as_deref();
        let mut fast = head.as_deref().and_then(|node| node.next.as_deref());

        while let (Some(s), Some(f)) = (slow, fast) {
            if std::ptr::eq(s, f) {
                return true;
            }

            slow = s.next.as_deref();
            fast = f.next.as_deref().and_then(|node| node.next.as_deref());
        }

        false
    }
}

Rust · runnable

function hasCycle(head: ListNode | null): boolean {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head?.next ?? null;

  while (slow !== null && fast !== null) {
    if (slow === fast) return true;
    slow = slow.next;
    fast = fast.next?.next ?? null;
  }

  return false;
}

TypeScript · runnable

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head.next if head else None

        while slow is not None and fast is not None:
            if slow is fast:
                return True
            slow = slow.next
            fast = fast.next.next if fast.next else None

        return False

Python · runnable

Trace

Floyd's algorithm on head = [3,2,0,-4] with the tail pointing back to 2:

step	slow	fast	result
start	3	2	different
1	2	-4	different
2	0	0	meet -> cycle

The pointers meet inside the cycle, so the answer is true.

Edge cases

Empty list — no cycle.
Single node with no self-loop — fast falls off immediately.
Single node with a self-loop — the pointers meet on the first iteration.
Long acyclic prefix before the cycle — the slow pointer may take a while to enter the loop, but once both pointers are inside the cycle, meeting is guaranteed.

Takeaway

Cycle detection is about identity and motion, not values. If you remember only one thing, remember this: a repeated node is a repeated pointer, and two pointers with different speeds on a closed loop must eventually coincide.

Easy#206

Reverse Linked List

Three pointers: prev, curr, next. Draw it out. Do both iterative and recursive.

Easy#21

Merge Two Sorted Lists

Merge step of merge sort. In Rust, practice with Option<Box<ListNode>>.

Medium#143

Reorder List

Combines three techniques: find middle, reverse second half, merge.

Problem

Intuition

Approach

Trace

Edge cases

Takeaway

More in Linked Lists