Given the head of a singly linked list, return True if following next pointers eventually revisits a node (the list contains a cycle), and False if the walk ends at None.
In the tests, cycles are built by pointing some node's next back at an earlier node, for example 1 -> 2 -> 3 -> 4 -> (back to 2).
Examples
Input: head = 1 -> 2 -> 3
Output: False
Input: head = 1 -> 2 -> 3 -> 4 -> (back to 2)
Output: True
Constraints
0 <= number of nodes <= 10**4- Values may repeat, so comparing values is not enough
- Target: O(n) time, O(1) extra space
Goals
- Detect a cycle without extra memory using two pointers at different speeds
- Compare node identity with `is`, not values