Given the head of a linked list, decide whether the list contains a cycle — whether following next forever would loop rather than reach the end. In the test data a cyclic list is written [3,2,0,-4]@1: the values in order, with the tail's next pointing back to the node at index 1. Your function receives only the head.
Examples
Example 1:
Input: head = [3,2,0,-4]@1
Output: true
Example 2:
Input: head = [1,2]@0
Output: true
Explanation: the tail points back at the head.
Example 3:
Input: head = [1]
Output: false
Example 4:
Input: head = []
Output: false
Linked lists — a node holds a value and a next reference, and rearranging a list means moving references, never values. Dummy heads: a node in front of the list so the first element stops being a special case. Two pointers on a list — one ahead of the other, or one moving twice as fast.
How to think about it
1. Remember Every Node
Intuition
Walk the list putting each node in a set; arriving at one already there means the walk went round. Straightforward, and the version worth stating before the pointer trick — the interviewer is usually asking you to beat its memory, not its correctness.
Algorithm
1. Walk from the head, adding each node to a set. 2. A node already in the set closes a cycle — return true. 3. Falling off the end means the list is straight.
Time & Space
Time O(n). Space O(n) — which is the thing to improve.
2. Tortoise and Hare Optimal
Intuition
Two runners on a circular track always meet; on a straight one, the faster simply finishes. Step one pointer once and the other twice: inside a loop the gap between them closes by exactly one each step, so they must land on the same node, and no memory is needed to prove it.
Algorithm
1. Start both pointers at the head. 2. Move slow one step and fast two. 3. Fast (or fast.next) reaching null means no cycle. 4. Slow and fast meeting means there is one.