linked-list-has-cycle.md

Requirements

Return true if a singly linked list has a loop.

Strategy

Use two pointers, the second moving twice the speed of the first, and see if the two pointers ever land on the same node.

Justification of strategy

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.

Define Test Cases

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

Implementation Skeleton

• 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

Actual implementation

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;
    
}