Dev Skills
Go·Go for coding rounds

Detect a cycle with two pointers

Floyd's tortoise and hare: find a loop in a linked list with no extra memory.

Topic 31 of 98 · 5 min to read · 45 min to build
After this topic you can
  • Write Floyd's cycle check with slow and fast pointers.
  • Explain why both fast and fast.Next must be checked for nil.
  • Predict where slow and fast meet on a small cyclic list.

The problem

Given the head of a linked list, return true if some node's Next points back to an earlier node, so walking it would never end.

Brute force first

Remember every node you visit in a map[*Node]bool. If you reach a node already in the map, there is a cycle; if you reach nil, there is not.

O(n) time, O(n) space. Correct and easy to explain; the follow-up is always "now do it in O(1) space".

The approach

The easy answer is a map[*Node]bool of visited nodes: O(n) time, O(n) space. Say it first.

Then the better one. Move slow one step and fast two steps. With no loop, fast reaches nil. With a loop, fast gains one node per step on slow and must land on it. O(n) time, O(1) space.

cycle.go
package main
import "fmt"
type Node struct {
	Val  int
	Next *Node
}
// hasCycle is Floyd's tortoise and hare: slow moves one step, fast moves two.
// If there is a loop, fast laps slow and they meet. If not, fast hits nil.
func hasCycle(head *Node) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast { // pointer comparison: the same node, not the same value
			return true
		}
	}
	return false
}
func main() {
	a := &Node{Val: 1}
	b := &Node{Val: 2}
	c := &Node{Val: 3}
	a.Next, b.Next = b, c
	fmt.Println(hasCycle(a))   // false
	c.Next = b                 // 3 points back to 2
	fmt.Println(hasCycle(a))   // true
	fmt.Println(hasCycle(nil)) // false
}

Dry run

1 → 2 → 3 → 4, and 4 points back to 2. Slow moves 1, fast moves 2:

stepslowfastsame node?
start11(not checked)
123no
232 (3 → 4 → 2)no
344 (2 → 3 → 4)yes, return true

Go-specific gotchas

  • Check `fast != nil && fast.Next != nil` before fast.Next.Next. Both are needed, or you get a nil pointer panic on even-length lists.
  • `slow == fast` compares pointers, which means "the same node". Comparing slow.Val == fast.Val is a bug when values repeat.
  • Pointers are valid map keys, so map[*Node]bool works for the simple version.
The short version
  • Map of visited nodes first, then two pointers for O(1) space.
  • Guard both fast and fast.Next.
  • Compare nodes, not values.
Remember: Two runners on a circular track always meet. On a straight one, the fast one just finishes.
Build this before moving on
Return the node where the cycle starts. Hint: after they meet, move one pointer back to the head and step both by one.
Coding challenge · checked by tests
Write hasCycle(head *Node) bool that reports whether the list loops back on itself, using Floyd's slow and fast pointers in O(1) extra space (the hidden tests check that it allocates nothing, so no "visited" map). Example: 1 → 2 → 3 → back to 2 → true.

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Return the node where the cycle starts. Hint: after they meet, move one pointer back to the head and step both by one.
  2. 2Dry run Floyd on 1 → 2 → 3 with no cycle. Why does the loop stop, and after how many steps?
  3. 3Find the length of the cycle, once you know there is one.
Official documentation
Check yourselfTake the Go for coding rounds test