Here is one way to determine the start of a circular linked list in JavaScript:
findCycleStartTry in REPL1 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; while (hare) { if (hare === turtle) break; turtle = turtle.next; hare = hare.next; hare = hare && hare.next; } if (hare === null) return null; 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.