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 !
Top comments (0)