Linked List Cycle
Given the head of a singly linked list, return true if there is a cycle in the linked list, otherwise return false.
There is a cycle in a linked list if at least one node in the list can be visited again by following the next pointer.
Constraints:
- The number of nodes in the list is in the range
[1, 1000]. - Node values are in the range
[-1000, 1000]. - The
indexparameter (not passed to the function) determines the index where the cycle begins, if it exists. Ifindex = -1, then no cycle exists.
Example 1:
Input: head = [1, 2, 3, 4], index = 1 Output: true
Example 2:
Input: head = [1], index = -1 Output: false
Recommended time and space complexity
You should aim for a solution with O(n) time complexity and O(1) space complexity for the optimal approach.
Hint 1
A brute force approach would be to use a hash table to store visited nodes. This would be an O(n) time and O(n) space solution. Can you think of a more efficient approach?
Hint 2
Can you use two pointers moving at different speeds to detect a cycle?
Hint 3
Use the "tortoise and hare" method (Floyd's algorithm) to detect a cycle without using additional memory.