Description
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
Example
Input: [1,2,3], tail connects to index 0, output: true
Input: [1, 2, 3], output: false
Idea
Use a slow pointer which advance once each time, a fast pointer which advance once each time.
If the linked list has no cycle, then the fast pointer will reach null.
Otherwise, they never stop, but will meet.
Solution
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;
ListNode *slow = head, *fast = head->next;
while (fast) {
if (slow == fast) return true;
slow = slow->next;
fast = fast->next;
if (!fast) return false;
fast = fast->next;
}
return false;
}
};
Performance
16 / 16 test cases passed.
Runtime: 6 ms
