Linked List Cycle in Go — Floyd's Tortoise & Hare & More

Linked List Cycle (#141 — Easy): Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.

Example:

Input: head = [3,2,0,-4], pos = 1 (tail connects to node index 1)
Output: true

Approach: Floyd’s Tortoise & Hare (Optimal)

Time: O(n) | Space: O(1)

Two pointers at different speeds: fast moves 2 steps, slow moves 1. If there’s a cycle, fast will eventually lap slow and they’ll meet. O(1) space.

type ListNode struct {
	Val  int
	Next *ListNode
}

func hasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast { return true }
	}
	return false
}

Approach: Hash Set

Time: O(n) | Space: O(n)

Store every visited node in a set. If we revisit a node, a cycle exists. Uses O(n) space but works even when you cannot modify the list.

func hasCycleSet(head *ListNode) bool {
	seen := make(map[*ListNode]bool)
	for head != nil {
		if seen[head] { return true }
		seen[head] = true
		head = head.Next
	}
	return false
}

Key Takeaways

• Start with the brute-force approach to understand the problem
• Floyd’s Tortoise & Hare (Optimal) gives the optimal O(n) solution
• Practice this pattern — it appears frequently in coding interviews

Related Problems

• Linked List Cycle in Python
• Linked List Cycle in Dart
• Linked List Cycle in Swift
• Remove Duplicates from Sorted Array in Go
• Reverse Linked List in Go
• Reverse String in Go

FAQ

What is the best approach to solve Linked List Cycle in Go?

The recommended approach is Floyd’s Tortoise & Hare (Optimal), which runs in O(n) time with O(1) space. The full Go implementation is shown above.

What is the time complexity of Linked List Cycle in Go?

Using Floyd’s Tortoise & Hare (Optimal), the time complexity is O(n) and the space complexity is O(1).

Happy coding!