Linked List Cycle

Easy

The problem

Given the head of a linked list, return true if the list has a cycle: some node's next pointer leads back to a node that was already visited, so following next never ends. Otherwise (the list ends in nil) return false.

Example 1
Input: head = [3, 2, 0, -4], and the last node's next points back to the node holding 2
Output: true
Following next goes 3, 2, 0, -4, 2, 0, -4, ... forever.
Example 2
Input: head = [1, 2], and the last node's next is nil
Output: false
The list ends after 2.
Example 3
Input: head = [1], and its next points to itself
Output: true
The single node loops back onto itself.

Limits

0 ≤ number of nodes ≤ 10,000
-100,000 ≤ node value ≤ 100,000
A list with no nodes has no cycle

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Two runners on a circular track at different speeds will eventually meet.

The idea

Slow moves 1 step, fast moves 2. If fast reaches nil there is no cycle; if they ever meet there is one.

Target: O(n) time, O(1) space

Go function shape

func hasCycle(head *ListNode) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// HasCycle: Floyd's tortoise and hare.
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 { // compare nodes (pointers), never values
			return true
		}
	}
	return false
}

Read the lesson: Linked List · Fast & Slow Pointers