Middle · Algorithms

Find a linked-list cycle entry with constant extra space

A list may contain a cycle after a non-cyclic prefix. How do you find its entry rather than merely report that some cycle exists?

Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.

EXAMPLE · FRAGMENT UNLESS A COMPLETE PROGRAM IS SHOWN

package main

import "fmt"

type Node struct {
	Value int
	Next  *Node
}

func entry(head *Node) *Node {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			p := head
			for p != slow {
				p = p.Next
				slow = slow.Next
			}
			return p
		}
	}
	return nil
}
func main() {
	a, b, c := &Node{Value: 1}, &Node{Value: 2}, &Node{Value: 3}
	a.Next = b
	b.Next = c
	c.Next = b
	fmt.Println(entry(a) == b, entry(nil) == nil)
}

Reveal a strong answer

Move slow by one link and fast by two while checking both fast and fast.Next before dereferencing. Meeting pointer identity proves a cycle; comparing node values would be incorrect because different nodes may hold equal values.
After a meeting, move one pointer from the head and one from the meeting point by one step. Their next meeting identifies the entry. Explain the relation between the non-cyclic prefix and the distance travelled around the cycle rather than memorizing an unexplained reset.
The algorithm assumes the next pointers do not change during traversal. It does not reclaim memory, synchronize concurrent mutation or solve arbitrary graph cycles. Test nil head, one acyclic node, a self-loop, repeated values and a cycle with a prefix. A visited-node map is a valid alternative when extra memory or a traversal history is useful.

Common trap

Equal values do not establish node identity, and mutating links while traversing invalidates the fixed-list argument.

Complexity & use

O(n) time and O(1) auxiliary space on a fixed singly linked list.

Try it

Build nodes 1→2→3→2, trace the two phases and then test a nil list and a self-loop.

Worked solution

The first phase either reaches nil safely or finds a meeting inside the cycle. Reset one pointer to head and advance both by one to locate the entry. Return the actual node pointer, not its potentially repeated value. Preserve the input and document exclusive or immutable access during traversal.

Change the constraint

What changes if the input is an arbitrary directed graph rather than a list with at most one next edge per node?

How did you do?

Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.

Not marked. Progress stays on this browser, separate from course completion.

Primary references

Checked 2026-10-28. Use documentation for your pinned runtime, driver and tool version.