How to determine the start of a circular linked list

Here is one way to determine the start of a circular linked list in JavaScript:

findCycleStartTry in REPL
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
function findCycleStart(head) {
if (!head) return null;
let turtle = head.next;
let hare = turtle && turtle.next;
// Phase 1 - cycle detection
while (hare) {
if (hare === turtle) break;
turtle = turtle.next;
hare = hare.next;
hare = hare && hare.next;
}
if (hare === null) return null;
// Phase 2 - identify start of cycle
turtle = head;
while (true) {
if (turtle === hare) return turtle;
turtle = turtle.next;
hare = hare.next;
}
}
function Node(data) {
this.next = null;
this.data = data;
}
Node.prototype.addToTail = function(data) {
const end = new Node(data);
let current = this;
while (current.next !== null) {
current = current.next;
}
current.next = end;
return end;
};

Tests can be found at REPL.it.