141. Linked List Cycle

At a Glance

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

Problem (one-liner)

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

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}

Walkthrough

Nodes 1 -> 2 -> 3 -> 2 (back to second). slow and fast both land on the same node inside the loop after sufficient steps.

Invariant: in a cycle, relative speed 1 guarantees meeting; without a cycle, fast exhausts the list.

Edge Cases

• Empty list — false.
• Self-loop on head — true immediately on second advance.
• Two-node cycle.

Pitfalls

• Starting fast one step ahead incorrectly — keep both at head for standard template.
• Not checking fast.Next before fast.Next.Next.

Similar Problems

• 142. Linked List Cycle II — find entry after detection.
• 287. Find the Duplicate Number — same pointer physics on an index graph.
• 19. Remove Nth Node From End of List — two-speed gap pattern.

Variants

• Length of cycle — after meet, count steps to meet again.
• Break the cycle — store meet point, then find entry (essentially 142).

Mind-Map Tags

#linked-list #floyd #cycle-detection #fast-slow