Linked-list cycle (beginner friendly)

Linked lists are data structures that contain a head, and nodes with a .value and a .next property. The next property connects to the following node so they can be traversed in order with the .next property.

// a linked list object with a head and node children
const linkedList = { head: {
                            next: {
                                    val: 1,
                                    next: {
                                            val: 2,
                                            next: null  
                                           }
                                   }
                           }   
                    }

This leetcode problem asks to find if any of the nodes on a linked list connects to a previous node on the list so it 'cycles' back.

The arguments to the function are the linked list values e.g. [1,2,3,4] and the position where the cycle is present for example: 1 which means the linked list goes back to the node at position index 1 after the final node. When -1 is passed there is no cycle.

const hasCycle = (head) => {
    let seen = []

    while(head !== null){

        if(seen.includes(head)){ // use includes method of array equivalent of contains to hashset in java
            return true
        }else{
            seen.push(head)
        }
        head = head.next
    }
    return false
};

In this solution we check to see if we go back to an earlier node while we traverse the linked list.

With the help of an array, we store the nodes as we visit them.

let seen = []
//...
// and when visiting them
//...
seen.push(head)

We simply use a while loop to traverse the linked list and reset head to head.next at the end of the loop. Which allows us to visit the next node on the subsequent iteration.

while(head !== null){
//... 
// condition checks
//... 
head = head.next
} 

Then use the .includes Array method to check if we already visited the current node by checking if it is already present on the seen array.

if(seen.includes(head)){ 
            return true
}else{
            seen.push(head)
}

Last, if we find the head has already been added to the seen array we return true as the function returns false otherwise by default.

Feel more than welcome to reach out on LinkedIn or Twitter !