Return true if a singly linked list has a loop.
Use two pointers, the second moving twice the speed of the first, and see if the two pointers ever land on the same node.
Consider two runners on a track. The faster runner will lap the slower one. The faster runner in our case is a pointer incremented douple the incrementation of the slower pointer.
The edge case we have to account for is when the slow or the fast or the immediate child of the fast node is null.
let linkedList = new LinkedList(); linkedList.add(1) linkedList.add(2) linkedList.add(3) hasCycle(linkedList) ==> false
linkedList.head.next.next = linkList.head.next hasCycle(linkedList) ==> true
- define slow and fast pointer set them equal to head
- while the slow pointer and the fast pointer and the next node after the fast pointer are not null
- increment the slow counter by setting it equal to the next node
- increment the fast counter by setting it equal to the next, next node
- if the slow node equals the fast node,
- return true
- break out of while loop and return false
var hasCycle = function(head, pointer) {
var slow = head,
fast = head;
while (slow && fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (fast === slow) {
return true;
}
}
return false;
}