Solving Linked List Cycle in Go: Step-by-Step Guide
The Linked List Cycle problem is one of the most classic algorithmic challenges you will encounter in technical interviews and real-world systems programming. It tests your understanding of pointers, memory, and algorithmic optimization. In this tutorial, we will walk through everything you need to know to detect cycles in a singly linked list using Go, from the underlying concepts to production-ready implementations.
What Is a Linked List Cycle?
A linked list is a linear data structure where each element (called a node) contains a value and a pointer to the next node. A cycle occurs when a node's next pointer references an earlier node in the list, creating a loop. Once a cycle exists, traversing the list naively will never terminate because you keep revisiting the same nodes.
Visually, a cyclic linked list looks like this:
1 -> 2 -> 3 -> 4 -> 5
^ |
|_________|
In this example, node 5 points back to node 3, forming a cycle. Any traversal that starts at the head and follows next pointers will loop forever between nodes 3, 4, and 5.
Why It Matters
Detecting cycles is not just an academic exercise. In real systems, cycles can cause catastrophic failures:
- Infinite loops: Traversal code that never terminates can hang services and exhaust CPU.
- Memory leaks: Garbage collectors in languages like Go use reachability analysis. A cycle that is still referenced may prevent nodes from being collected, leaking memory.
- Serialization bugs: Serializing a cyclic structure without cycle detection causes stack overflows or infinite recursion.
- Graph-like data: Many graph algorithms reduce to cycle detection on adjacency structures built from linked nodes.
Understanding cycle detection also builds intuition for more advanced topics such as topological sorting, deadlock detection, and iterative object graph traversal.
Defining the Linked List in Go
Before solving the problem, we need a concrete representation of a linked list node. In Go, we use a struct with a pointer to the next node.
package main
import "fmt"
// ListNode represents a node in a singly linked list.
type ListNode struct {
Val int
Next *ListNode
}
// NewListNode creates a new node with the given value.
func NewListNode(val int) *ListNode {
return &ListNode{Val: val}
}
This simple struct is all we need. The Next pointer is what makes the structure a linked list, and it is also what makes cycles possible.
Building a Cyclic List for Testing
To test our cycle detection code, we need a helper that constructs a list with a cycle at a specific position. The pos parameter indicates the index of the node that the tail should point back to. A pos of -1 means no cycle.
// BuildCyclicList builds a linked list from a slice of values
// and creates a cycle by connecting the tail to the node at index pos.
// If pos is -1, the list has no cycle.
func BuildCyclicList(values []int, pos int) *ListNode {
if len(values) == 0 {
return nil
}
head := NewListNode(values[0])
nodes := []*ListNode{head}
current := head
for i := 1; i < len(values); i++ {
node := NewListNode(values[i])
current.Next = node
current = node
nodes = append(nodes, node)
}
if pos >= 0 && pos < len(nodes) {
current.Next = nodes[pos]
}
return head
}
By storing each node in a slice as we build the list, we can easily connect the tail back to any earlier node, simulating a cycle.
Approach 1: Hash Set Tracking
The most intuitive solution is to track every node we visit in a hash set. If we encounter a node we have already seen, a cycle exists. If we reach nil, the list is acyclic.
Implementation
// HasCycleSet returns true if the linked list contains a cycle.
// It uses a hash set to track visited nodes.
func HasCycleSet(head *ListNode) bool {
visited := make(map[*ListNode]bool)
current := head
for current != nil {
if visited[current] {
return true
}
visited[current] = true
current = current.Next
}
return false
}
Complexity Analysis
- Time complexity: O(n), where n is the number of nodes. We visit each node at most once.
- Space complexity: O(n), because we store every visited node in the map.
This approach is simple and correct, but the O(n) memory usage is wasteful for large lists. In constrained environments or when processing millions of nodes, we can do better.
Approach 2: Floyd's Tortoise and Hare Algorithm
Floyd's algorithm is the optimal solution. It uses two pointers moving at different speeds: a slow pointer (the tortoise) that moves one step at a time, and a fast pointer (the hare) that moves two steps at a time. If there is a cycle, the fast pointer will eventually lap the slow pointer and they will meet. If there is no cycle, the fast pointer will reach nil.
Why It Works
Imagine both pointers are inside the cycle. Each iteration, the distance between the fast and slow pointer changes by one step. Because the cycle has a finite length, the fast pointer must eventually catch up to the slow pointer. This is guaranteed regardless of where each pointer enters the cycle.
Implementation
// HasCycleFloyd returns true if the linked list contains a cycle.
// It uses Floyd's tortoise and hare algorithm with O(1) space.
func HasCycleFloyd(head *ListNode) bool {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
The loop condition fast != nil && fast.Next != nil is critical. We must check both because the fast pointer advances by two nodes. If fast.Next is nil, advancing would cause a nil pointer dereference.
Complexity Analysis
- Time complexity: O(n). In the worst case, the pointers traverse the list linearly before meeting.
- Space complexity: O(1). We only use two pointers regardless of list size.
This is the preferred solution in interviews and production code because it achieves optimal time and space complexity.
Finding the Cycle Start Node
Detecting a cycle is often only the first step. In many problems, you also need to find the node where the cycle begins. Floyd's algorithm can be extended to do this with no additional memory.
The Insight
When the slow and fast pointers meet, the slow pointer has traveled a distance equal to the distance from the head to the cycle start plus some distance inside the cycle. By resetting one pointer to the head and moving both pointers one step at a time, they will meet exactly at the cycle start.
Implementation
// DetectCycleStart returns the node where the cycle begins,
// or nil if there is no cycle.
func DetectCycleStart(head *ListNode) *ListNode {
slow := head
fast := head
// Phase 1: detect whether a cycle exists.
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
// Phase 2: find the start of the cycle.
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
}
return nil
}
Phase 1 is identical to the basic detection. Phase 2 resets the slow pointer to the head and advances both pointers one step at a time. The node where they meet is the cycle entry point.
Putting It All Together
Let us write a complete, runnable program that demonstrates both approaches and the cycle start detection.
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func NewListNode(val int) *ListNode {
return &ListNode{Val: val}
}
func BuildCyclicList(values []int, pos int) *ListNode {
if len(values) == 0 {
return nil
}
head := NewListNode(values[0])
nodes := []*ListNode{head}
current := head
for i := 1; i < len(values); i++ {
node := NewListNode(values[i])
current.Next = node
current = node
nodes = append(nodes, node)
}
if pos >= 0 && pos < len(nodes) {
current.Next = nodes[pos]
}
return head
}
func HasCycleSet(head *ListNode) bool {
visited := make(map[*ListNode]bool)
current := head
for current != nil {
if visited[current] {
return true
}
visited[current] = true
current = current.Next
}
return false
}
func HasCycleFloyd(head *ListNode) bool {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
func DetectCycleStart(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
}
return nil
}
func main() {
// Build a list: 1 -> 2 -> 3 -> 4 -> 5, with tail pointing back to index 2.
cyclicHead := BuildCyclicList([]int{1, 2, 3, 4, 5}, 2)
fmt.Println("HasCycleSet: ", HasCycleSet(cyclicHead))
fmt.Println("HasCycleFloyd: ", HasCycleFloyd(cyclicHead))
start := DetectCycleStart(cyclicHead)
if start != nil {
fmt.Println("Cycle starts at node with value:", start.Val)
}
// Build an acyclic list.
acyclicHead := BuildCyclicList([]int{1, 2, 3, 4, 5}, -1)
fmt.Println("Acyclic HasCycleFloyd:", HasCycleFloyd(acyclicHead))
fmt.Println("Acyclic cycle start: ", DetectCycleStart(acycHead))
}
When you run this program, the output should be:
HasCycleSet: true
HasCycleFloyd: true
Cycle starts at node with value: 3
Acyclic HasCycleFloyd: false
Acyclic cycle start: <nil>
Best Practices
- Prefer Floyd's algorithm: It offers O(1) space and is easy to implement. Reserve the hash set approach for cases where you also need to store metadata about each visited node.
- Guard against nil: Always check
fast != nil && fast.Next != nilbefore advancing the fast pointer. Forgetting this check is the most common source of panics. - Test edge cases: Include tests for empty lists, single-node lists, single-node self-loops, and long acyclic lists. These boundary cases often expose subtle bugs.
- Avoid mutating the list: Some clever solutions mark nodes as visited by modifying their values, but this corrupts the data. Prefer non-destructive approaches unless you explicitly own and can discard the data.
- Document cycle assumptions: If your function assumes the input list is acyclic, state that clearly in the documentation. Silent infinite loops are worse than explicit panics.
- Use table-driven tests: Go's testing package makes table-driven tests natural. Cover multiple
posvalues and list lengths in a single test function.
Example Table-Driven Test
package main
import "testing"
func TestHasCycleFloyd(t *testing.T) {
tests := []struct {
name string
values []int
pos int
want bool
}{
{"empty list", []int{}, -1, false},
{"single node no cycle", []int{1}, -1, false},
{"single node self loop", []int{1}, 0, true},
{"no cycle", []int{1, 2, 3, 4, 5}, -1, false},
{"cycle at head", []int{1, 2, 3}, 0, true},
{"cycle in middle", []int{1, 2, 3, 4, 5}, 2, true},
{"cycle at tail", []int{1, 2, 3}, 2, true},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
head := BuildCyclicList(tt.values, tt.pos)
got := HasCycleFloyd(head)
if got != tt.want {
t.Errorf("HasCycleFloyd() = %v, want %v", got, tt.want)
}
})
}
}
Conclusion
Detecting a cycle in a linked list is a foundational problem that teaches pointer manipulation, algorithmic optimization, and defensive programming. The hash set approach is intuitive and useful when you need to track additional metadata, but Floyd's tortoise and hare algorithm is the gold standard for its O(n) time and O(1) space complexity. By extending Floyd's algorithm with a second phase, you can also locate the exact node where a cycle begins, all without modifying the original list. Master these techniques, write thorough table-driven tests, and always guard against nil pointers, and you will be well equipped to handle cycle detection problems in both interviews and production Go codebases.