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.
public
class Solution {
public boolean hasCycle(ListNode head) {
ListNode tortoise = head;
ListNode hare = head;
while (hare != null && hare.next != null) {
tortoise = tortoise.next;
hare = hare.next.next;
if (tortoise == hare) return true;
}
return false;
}
}Follow-up:
How would you find the start of the cycle in the linked list?
