-
Notifications
You must be signed in to change notification settings - Fork 8
/
Copy pathCan you get the loop ?.js
48 lines (39 loc) · 1.31 KB
/
Can you get the loop ?.js
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
/*
Description:
You are given a node that is the beginning of a linked list. This list always contains a tail and a loop.
Your objective is to determine the length of the loop.
For example in the following picture the tail's size is 3 and the loop size is 11.
Image and video hosting by TinyPic
// Use the `getNext' method or 'next' property to get the following node.
node.getNext()
node.next
Note: do NOT mutate the nodes!
Thanks to shadchnev, I broke all of the methods from the Hash class.
Don't miss dmitry's article in the discussion after you pass the Kata !!
*/
function loop_size(node){
var turtle = node;
var rabbit = node;
// Find a point in the loop. Any point will do!
// Since the rabbit moves faster than the turtle
// and the kata guarantees a loop, the rabbit will
// eventually catch up with the turtle.
do {
turtle = turtle.getNext();
rabbit = rabbit.getNext().getNext();
}
while (turtle != rabbit);
// The turtle and rabbit are now on the same node,
// but we know that node is in a loop. So now we
// keep the turtle motionless and move the rabbit
// until it finds the turtle again, counting the
// nodes the rabbit visits in the mean time.
var count = 0;
do {
++count;
rabbit = rabbit.getNext();
}
while (turtle != rabbit);
// voila
return count;
}