142. Linked List Cycle II

Quick Identifier

• Topic: linked-list
• Pattern: Fast & Slow Pointers (Floyd + entry)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Apple
• Frequency: Very High
• LeetCode: 142

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(1) from the optimal approach.
• Core Mechanism: If a singly linked list has a cycle, return the first node in the cycle; if no cycle, return nil.

Concept Explanation

If a singly linked list has a cycle, return the first node in the cycle; if no cycle, return nil.

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:

• Part two of 141: need the start of the loop, not just boolean
• After slow and fast meet, move one pointer to head, advance both one step at a time until they meet at entry
• Math: distance from head to entry equals distance from meet point to entry along the loop

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.

Approaches

• Brute force — O(n) space — set of seen nodes, first repeat is entry.
• Better — not needed.
• Optimal — O(n) time / O(1) space — detect meet, then reset one pointer to head and walk in lockstep.

Optimal Solution

Go

type ListNode struct {
	Val  int
	Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	slow, fast := head, 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
}

JavaScript

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

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

Walkthrough

List 3 -> 2 -> 0 -> -4 with tail to index 1 (value 2).

Edge Cases

• No cycle — first loop ends with fast nil.
• Cycle is entire list — entry is head.
• Self-loop on last node.

Pitfalls

• Returning meet point from phase one — that is not the entry in general.
• Reusing fast without keeping the meeting fast for second phase — you need the meeting node to walk with the head pointer; the code reuses fast from the meeting point (both travel at speed 1).

Similar Problems

• 141. Linked List Cycle — existence only.
• 287. Find the Duplicate Number — same entry formula on an index array.
• 202. Happy Number — cycle detection in value space.

Variants

• Find length of loop — from entry, walk until you return to entry.
• Unordered list with external ids — same math; store nothing extra if list nodes only.

Mind-Map Tags

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