Linked List Cycle
Given the head of a linked list, return true if the linked list has a cycle, or false otherwise.
Constraints:
- The number of the nodes in the list is in the range [0, 10^4].
- The value of the nodes in the list is in the range [-10^5, 10^5].
- 0 <= Node.val <= 10^5
- The list is guaranteed to be non-empty and may contain cycles.
Examples:
Input: [1,2,3,4,5] with a cycle at node 3
Output: true
Explanation: There is a cycle in the linked list, where the last node (5) points back to the node at index 3.
Input: [1,2,3,4,5] with no cycle
Output: false
Explanation: There is no cycle in the linked list.
Solutions
Two Pointers (Floyd's Tortoise and Hare)
Time: O(n)Space: O(1)
The two pointers start at the head of the list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer. If there is no cycle, the fast pointer will reach the end of the list.
class Solution:
def hasCycle(self, head:
ListNode) -> bool:
tortoise = head; hare = head; while hare and hare.next:
tortoise = tortoise.next; hare = hare.next.next; if tortoise === hare:
return True; return FalseFollow-up:
How would you find the start of the cycle in the linked list?
