141. Linked List Cycle

Quick Identifier

Topic: linked-list
Pattern: Fast & Slow Pointers (Floyd’s cycle)
Difficulty: Easy
Companies: Amazon, Google, Meta, Apple, Microsoft
Frequency: Very High
LeetCode: 141

Quick Sights

Time Complexity: O(n) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Given the head of a linked list, return true if some node is revisited by following Next (a cycle), otherwise false.

Concept Explanation

Given the head of a linked list, return true if some node is revisited by following Next (a cycle), otherwise false.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

“Cycle” in a singly linked list
O(1) memory often required
Fast moves two steps, slow moves one; they meet iff cycle exists

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — O(n) time / O(n) space — hash visited nodes.
Better — not needed.
Optimal — O(n) time / O(1) space — Floyd: if fast and slow meet, cycle; if fast hits nil, no cycle.

Optimal Solution

Go

type ListNode struct {
	Val  int
	Next *ListNode
}

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

JavaScript

class ListNode {
	constructor(val = 0, next = null) {
		this.val = val;
		this.next = next;
	}
}

function hasCycle(head) {
	if (head === null) {
		return false;
	}
	let slow = head;
	let fast = head;
	while (fast !== null && fast.next !== null) {
		slow = slow.next;
		fast = fast.next.next;
		if (slow === fast) {
			return true;
		}
	}
	return false;
}