Edit Problem

Title

Problem URL

Difficulty

Tags

Fast & Slow Pointers

Go file path (optional)

Notes (optional)

## What It Does

This function detects whether a singly linked list contains a cycle (i.e. a node whose `Next` pointer points back to an earlier node, forming a loop). It uses **Floyd's Cycle Detection algorithm** — also called the "tortoise and hare" — where `slow` advances one node at a time and `fast` advances two. If there's a cycle, `fast` will eventually lap `slow` and they'll meet at the same node. If there's no cycle, `fast` will hit `nil` and the loop exits cleanly.

For example, `1 → 2 → 3 → 4 → 2 (cycle)` — `slow` and `fast` will eventually both point to the same node somewhere in the `2 → 3 → 4` loop, returning `true`. For `1 → 2 → 3 → nil`, `fast` reaches `nil` and the function returns `false`.

---

## Complexity Analysis

**Time Complexity: O(n)**
In the no-cycle case, `fast` reaches `nil` after traversing ~n/2 iterations. In the cycle case, once `fast` enters the cycle it takes at most `cycle_length` steps to catch `slow`. Either way, the total steps are bounded linearly by the number of nodes.

**Space Complexity: O(1)**
Only two pointers (`slow` and `fast`) are maintained regardless of list size — no auxiliary data structures, no recursion stack.

---

## A Few Notes

**Why check `fast.Next != nil` and not just `fast != nil`?** Because `fast.Next.Next` would panic on a nil dereference if `fast.Next` is `nil`. Both guards are necessary for even-length lists where `fast` lands exactly on the last node.

**Why not use a hash set?** Storing visited node pointers in a `map[*ListNode]bool` would also work and is arguably more intuitive, but costs O(n) space. Floyd's gets you the same answer in O(1) — the standard tradeoff when you know you're just detecting presence, not finding the cycle entry point.

**Cycle entry detection is a natural extension.** If you needed to find *where* the cycle begins (not just whether one exists), you'd reset `slow` to `head` after they meet and advance both one step at a time — they'd meet again at the cycle entry node. This function stops short of that.

First solved

May 20, 2026