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.cpp
1class Solution {
2public:
3 bool hasCycle(ListNode* head) {
4 // Your code here
5 return false;
6 }
7};
Solution
Solve the problem first before reviewing the solution!