Question: How to determine if a linked list has a cycle? The Singly Linked List is defined as follows:
1 2 3 4 5 | struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; |
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};Using O(n) Hashset
With hashset, this becomes straightforward to store the visited nodes:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: bool hasCycle(ListNode *head) { unordered_set<ListNode*> visited; if (head == NULL) { return false; } while (head) { if (visited.count(head)) { return true; // has appeared before } visited.insert(head); head = head->next; } return false; } }; |
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> visited;
if (head == NULL) {
return false;
}
while (head) {
if (visited.count(head)) {
return true; // has appeared before
}
visited.insert(head);
head = head->next;
}
return false;
}
};Hashset/Hashmap normally has O(n) space complexity.
Fast and Slow Pointers
The O(1) space complexity solution uses two pointers: fast and slow. The fast pointer always advances every two nodes while the slow pointer advances one node at a time. If they somehow meet in the middle, we have a loop.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: bool hasCycle(ListNode *head) { if (head == NULL) { return false; } auto fast = head, slow = head; while (fast && slow && fast->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) { return true; } } return false; } }; |
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == NULL) {
return false;
}
auto fast = head, slow = head;
while (fast && slow && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
return true;
}
}
return false;
}
};This approaches work because given any length cycle, starting same node, two pointers will meet eventually.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
262 wordsloading...
Last Post: How to Fix Corruption in Resource Version Files?
Next Post: Adsense Brings The Page-Level Ads
