Edit Problem
Title
Problem URL
Difficulty
Easy
Medium
Hard
Tags
Fast & Slow Pointers
×
+ Two Pointers
Add tag
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
Clear
Save Changes
Cancel