“Linked List Cycle” Javascript Solution Cheat Sheet

The Linked List Cycle List is in the easy category and is a good start for understanding more challenging algorithms using a linked list as a data structure. I will focus on explaining a solution that works and not on the O time and space complexity.

Challenge:

”Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false.“LeetCode

Note:

//Linked list data structure.
//Pos is the index of the node that the tail point to.
//If pos exist return true else false.

Example:

 next    
  |            
4 -> 3 -> 0 -> -5
|    ^         |
Head |       Tail
     |         |
     |_________|
Input: head = [4,3,0,-5], pos = 1

Explanation:

Use two pointers that loop through the list at a different speed if they meet pos exist return true else return false.

1.Create a variable to keep track of the pointers.

fast = head;
slow = head;

2.Fast and Slow pointers loop through the list.

while(fastPointer !== null && fastPointer.next !== null){

3.Slow and Fast pointers have different speeds, slow advance by 1 and fast advance by 2.

fast = fast.next.next;

slow = slow.next;

4.Check if Fast and Slow pointers meet in the linked list.

if (fast === slow){

5.Return boolean value.

return true;

return false;

Solution :

var hasCycle = function(head) {
let fast = head;
let slow = head;
while(fast !== null && fast.next !== null){
fast = fast.next.next;
slow = slowPointer.next;
if (fast === slow){
return true;
}
}
return false;
};