-
Notifications
You must be signed in to change notification settings - Fork 14
/
Checking_cycle.h
40 lines (34 loc) · 1.1 KB
/
Checking_cycle.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Copyright (c) 2013 Elements of Programming Interviews. All rights reserved.
#ifndef SOLUTIONS_CHECKING_CYCLE_H_
#define SOLUTIONS_CHECKING_CYCLE_H_
#include <memory>
#include "./Linked_list_prototype.h"
// @include
shared_ptr<ListNode<int>> has_cycle(const shared_ptr<ListNode<int>>& head) {
shared_ptr<ListNode<int>> fast = head, slow = head;
while (slow && slow->next && fast && fast->next && fast->next->next) {
slow = slow->next, fast = fast->next->next;
if (slow == fast) { // there is a cycle.
// Calculates the cycle length.
int cycle_len = 0;
do {
++cycle_len;
fast = fast->next;
} while (slow != fast);
// Tries to find the start of the cycle.
slow = head, fast = head;
// Fast pointer advances cycle_len first.
while (cycle_len--) {
fast = fast->next;
}
// Both pointers advance at the same time.
while (slow != fast) {
slow = slow->next, fast = fast->next;
}
return slow; // the start of cycle.
}
}
return nullptr; // no cycle.
}
// @exclude
#endif // SOLUTIONS_SWAP_BITS_H_