Linked List Cycle
EasyLinked List
You are given head, the first node of a singly linked list. Return True if the list contains a cycle, and False otherwise.
A list has a cycle when some node can be reached again by repeatedly following next pointers, so walking the list never reaches None. Only node identity matters: two different nodes that happen to hold the same value do not form a cycle.
How the tests describe a list: each example shows the node values plus an index pos. The last node's next points to the node at index pos, or to None when pos is -1. pos is only used to build the input; your method receives just head.
Follow-up: can you do it with O(1) extra memory?
Example 1
- Input:
- head = [5,8,2,6,1], pos = 2
- Output:
- True
- Explanation
- The last node (value
1) points back to the node at index 2 (value2), so followingnextgoes 2, 6, 1, 2, 6, 1, ... forever.
Example 2
- Input:
- head = [4,4,4], pos = -1
- Output:
- False
- Explanation
- All three values are equal, but they are three different nodes and the last one points to
None, so the walk ends.
Example 3
- Input:
- head = [7], pos = 0
- Output:
- True
- Explanation
- The only node's
nextis itself, which is a cycle of length 1.
Constraints
- The number of nodes is in the range
[0, 10^4] -10^5 <= Node.val <= 10^5posis-1or a valid index in the list