141. Linked List Cycle
You are given head, the entry point of a singly linked list. Each node carries an integer val and a next pointer. Most lists end cleanly: follow next long enough and you reach null. Here, though, the final node may have been wired back to an earlier node, so a walk along the list would circle forever.
Return true if the list contains such a cycle, and false if the walk terminates at null.
Only for building the test lists, the input supplies an integer pos: the 0-based index of the node that the tail connects back to, or -1 when the tail points at nothing. Your function is never shown pos — it receives only head.
Can you decide the answer with O(1) extra memory?
Example 1:
Input: head = [3, 2, 0, -4], pos = 1
Output: true
Explanation: The tail node (value -4) links back to the node at index 1 (value 2), so a walk from head never reaches null.
Example 2:
Input: head = [1, 2], pos = -1
Output: false
Explanation: The tail's next pointer is null, so the walk ends after two steps.
Constraints:
- 0 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
- pos is -1 or a valid 0-based index into the list
Hints:
A cycle means exactly one thing: some node gets visited twice. Store every node you pass in a hash set (the node object, not its value — values can repeat) and stop the moment you meet a familiar one.
To drop the O(n) memory, race two pointers: slow moves one step per round, fast moves two. On a straight track the fast one falls off the end; on a circular track it must eventually land on the slow one — the gap between them shrinks by exactly one node per round.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [3, 2, 0, -4], pos = 1
Expected output: true