33 lines
1.1 KiB
C++
33 lines
1.1 KiB
C++
// https://leetcode.com/problems/linked-list-cycle/
|
|
// This is my intial, unthoughtful solution.
|
|
// Looking at the answers, it would turn out there's a much better method, involving two pointers, which didn't occur to me when I was originally trying to solve it.
|
|
// It seemed impossible to me to "remember" whether we've "seen" a specific node before so as to tell whether a cycle has occurred - the type of reasoning being used in this solution -
|
|
// but such reasoning is unnecessary under the other method. Please see 141b for that implementation.
|
|
|
|
/**
|
|
* Definition for singly-linked list.
|
|
*/
|
|
#include <cstddef>
|
|
#include <unordered_set>
|
|
struct ListNode {
|
|
int val;
|
|
ListNode *next;
|
|
ListNode(int x) : val(x), next(NULL) {}
|
|
};
|
|
|
|
class Solution {
|
|
public:
|
|
bool hasCycle(ListNode *head) {
|
|
std::unordered_set<ListNode*> seen;
|
|
ListNode* current = head;
|
|
while (current) {
|
|
if (seen.count(current)) {
|
|
return true;
|
|
}
|
|
seen.insert(current);
|
|
current = current->next;
|
|
}
|
|
return false;
|
|
}
|
|
};
|