mediumLinked ListTwo PointersFloyd's Tortoise & Hare
Linked List Cycle
Est. Time: 20 minTime: O(n)Space: O(1)
Description
Given the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if a node can be reached again by continuously following the next pointer.
Examples
Example 1 Input:head = [3,2,0,-4], pos = 1
Output:true
Explanation: Tail connects to node at index 1.
Example 2 Input:head = [1], pos = -1
Output:false
Constraints
▪The number of nodes is in the range [0, 10^4].
▪Node values range from -10^5 to 10^5.
Hints
Hint 1Show
Use Floyd's Tortoise and Hare algorithm.
Hint 2Show
Have two pointers: one moving one step at a time, the other two steps.
Hint 3Show
If they meet, there's a cycle.
Starter Code
Solution.java
1public class Solution {
2 public boolean hasCycle(ListNode head) {
3 // Your code here
4 return false;
5 }
6}
Solution
Solve the problem first before reviewing the solution!