Linked List Cycle

Problem

Given the head of a linked list, return True if the list contains a cycle (some node's next points back to a previous node), False otherwise.

Input: 1->2->3->4->2 (4 points back to 2)  → True
Input: 1->2->3->None                        → False
Input: None                                 → False

Solution

Approach: Floyd's tortoise-and-hare cycle detection.

Run two pointers from the head: slow advances one node per step, fast advances two. The loop guard while fast and fast.next is what keeps the two-step jump safe - fast guards against a None head or tail, and fast.next guards the second hop so fast.next.next never dereferences None. After each pair of moves, check slow is fast with identity (not value equality), because two distinct nodes can share a value and we care about landing on the same node object.

Correctness rests on a closing-gap argument. If the list ends, fast runs off it first and the loop exits with False. If there is a cycle, both pointers eventually enter it, and from then on fast gains exactly one node on slow every step. A gap that shrinks by one each iteration must reach zero, so they collide - and since the gap is at most the cycle length, that happens within O(n) steps, not O(n squared). Trace 1->2->3->1: start both at 1; step one gives slow=2, fast=3; step two gives slow=3, fast=2 (fast wraps 3->1->2); step three gives slow=1, fast=1, a collision, so return True.

Edge cases: An empty list fails fast on the first guard check and returns False. A single self-looping node (node.next = node) collides on the first iteration and returns True.

Complexity: O(n) time, O(1) space - two pointers, no auxiliary storage.