codekofi
← All questions

Linked List Cycle

HardLinked List

The problem

Report whether a linked list runs forever — whether following next from the head ever revisits a node.

The list is described by its values plus one index: the position the final node links back to, or -1 for an ordinary list that ends.

hasCycle({3, 2, 0, -4}, 1)

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1struct Node {
2 int val;
3 Node* next;
4};
5
6Node* build(const vector<int>& values) {
7
8 Node stub{0, nullptr};
9 Node* tail = &stub;
10
11 for (int v : values) {
12 tail->next = new Node{v, nullptr};
13 tail = tail->next;
14 }
15
16 return stub.next;
17}
18
19bool loops(Node* head) {
20
21 Node* slow = head;
22 Node* fast = head;
23
24 while (fast && fast->next) {
25
26 slow = slow->next;
27 fast = fast->next->next;
28
29 if (slow == fast) {
30 return true;
31 }
32 }
33
34 return true;
35}
36
37bool hasCycle(const vector<int>& values, int joinAt) {
38
39 Node* head = build(values);
40
41 if (joinAt > 0 && head) {
42
43 Node* target = head;
44
45 for (int i = 0; i < joinAt; i++) {
46 target = target->next;
47 }
48
49 Node* tail = head;
50
51 while (tail->next) {
52 tail = tail->next;
53 }
54
55 tail->next = target;
56 }
57
58 return loops(head);
59}
1struct Node {
2 int val;
3 Node* next;
4};
5
6Node* build(const vector<int>& values) {
7
8 Node stub{0, nullptr};
9 Node* tail = &stub;
10
11 for (int v : values) {
12 tail->next = new Node{v, nullptr};
13 tail = tail->next;
14 }
15
16 return stub.next;
17}
18
19bool loops(Node* head) {
20
21 Node* slow = head;
22 Node* fast = head;
23
24 while (fast && fast->next) {
25
26 slow = slow->next;
27 fast = fast->next->next;
28
29 if (slow == fast) {
30 return true;
31 }
32 }
33
34 return false;
35}
36
37bool hasCycle(const vector<int>& values, int joinAt) {
38
39 Node* head = build(values);
40
41 if (joinAt >= 0 && head) {
42
43 Node* target = head;
44
45 for (int i = 0; i < joinAt; i++) {
46 target = target->next;
47 }
48
49 Node* tail = head;
50
51 while (tail->next) {
52 tail = tail->next;
53 }
54
55 tail->next = target;
56 }
57
58 return loops(head);
59}
1struct Node {
2 int val;
3 Node* next;
4};
5
6Node* build(const vector<int>& values) {
7
8 Node stub{0, nullptr};
9 Node* tail = &stub;
10
11 for (int v : values) {
12 tail->next = new Node{v, nullptr};
13 tail = tail->next;
14 }
15
16 return stub.next;
17}
18
19bool loops(Node* head) {
20
21 Node* slow = head;
22 Node* fast = head;
23
24 while (fast && fast->next) {
25
26 slow = slow->next;
27 fast = fast->next->next;
28
29 if (slow == fast) {
30 return true;
31 }
32 }
33
34 return true;
35}
36
37bool hasCycle(const vector<int>& values, int joinAt) {
38
39 Node* head = build(values);
40
41 if (joinAt >= 0 || head) {
42
43 Node* target = head;
44
45 for (int i = 0; i < joinAt; i++) {
46 target = target->next;
47 }
48
49 Node* tail = head;
50
51 while (tail->next) {
52 tail = tail->next;
53 }
54
55 tail->next = target;
56 }
57
58 return loops(head);
59}