34 lines
1.2 KiB
C++
34 lines
1.2 KiB
C++
// https://leetcode.com/problems/linked-list-cycle/
|
|
/**
|
|
* Definition for singly-linked list.
|
|
*/
|
|
#include <cstddef>
|
|
struct ListNode {
|
|
int val;
|
|
ListNode *next;
|
|
ListNode(int x) : val(x), next(NULL) {}
|
|
};
|
|
|
|
// Reasoning:
|
|
// If we use two pointers, one that moves twice as fast as the other, then the faster one will
|
|
// eventually lap the slower one if there's a cycle, as it will go all the way back and catch up to it again.
|
|
// In this case, the pointers will eventually become equal, and we can return true, that there is a cycle;
|
|
// otherwise, the faster pointer will simply reach the end of the list, so either it or its successor will be null;
|
|
// in this case, there must not be a cycle, as it has simply reached the end.
|
|
// This begs the question whether this can be done in "O(1)" time by just iterating 10^4 times (as specified as the upper limit of the list's length in the problem).
|
|
class Solution {
|
|
public:
|
|
bool hasCycle(ListNode *head) {
|
|
ListNode* slow = head;
|
|
ListNode* fast = head;
|
|
while (fast && fast->next) {
|
|
fast = fast->next->next;
|
|
slow = slow->next;
|
|
if (fast == slow) {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
};
|