Repository navigation
Expand file tree
/
Copy pathLinkedListCycleII.cpp
More file actions
121 lines (109 loc) · 2.21 KB
/
Copy pathLinkedListCycleII.cpp
File metadata and controls
121 lines (109 loc) · 2.21 KB
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
void printList(ListNode * head) {
ListNode *cur = head;
while (cur) {
cout << cur->val << " ";
cur = cur->next;
}
puts("");
}
bool hasCycle(ListNode *head, ListNode* &nodeInCycle) {
if (head == NULL) {
return false;
}
ListNode *slow = head;
ListNode *fast = head->next;
while (fast && fast->next) {
if (fast == slow) {
nodeInCycle = fast;
return true;
} else {
slow = slow->next;
fast = fast->next->next;
}
}
return false;
}
ListNode * firstCommonNode(ListNode *ahead, ListNode *bhead) {
if (ahead==NULL || bhead==NULL) {
return NULL;
}
int lena = 0;
ListNode * acur = ahead;
while (acur) {
++lena;
acur = acur->next;
}
int lenb = 0;
ListNode *bcur = bhead;
while(bcur) {
++lenb;
bcur = bcur->next;
}
acur = ahead;
bcur = bhead;
//cout << lena << " -> ";
//printList(acur);
//cout << lenb << " -> ";
//printList(bcur);
if (lena > lenb) {
for (int i = 0; i < lena-lenb; ++i) {
acur = acur->next;
}
} else if (lenb > lena) {
for (int i = 0; i < lenb-lena; ++i) {
bcur = bcur->next;
}
}
while (acur != bcur) {
acur = acur->next;
bcur = bcur->next;
}
return acur;
}
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
ListNode *nodeInCycle = NULL;
if (!hasCycle(head, nodeInCycle)) {
return NULL;
}
//cout << "returned Node " << nodeInCycle->val << " next " << nodeInCycle->next->val << endl;
ListNode * chead = nodeInCycle->next;
nodeInCycle->next = NULL;
//printList(head);
//printList(chead);
return firstCommonNode(head, chead);
}
int main() {
ListNode *vhead = new ListNode(0);
int n;
cin >> n;
ListNode *cur = vhead;
for (int i = 0; i < n; ++i) {
cur->next = new ListNode(i);
cur = cur->next;
}
int cycleIndx;
cin >> cycleIndx;
ListNode * cycle = vhead->next;
for (int i = 0; i < cycleIndx; ++i) {
cycle = cycle->next;
}
cout << "Should be " << cycle->val << endl;
cur->next = cycle;
if (cur = detectCycle(vhead->next)) {
cout << "Actually is " << cur->val << endl;
} else {
cout << "Not A cycle" << endl;
}
return 0;
}