We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I think your confusion is like mine in at first assuming that the fast node is skipping a node while it is going "twice as fast". In reality it is not as fast.next.next is actually referencing the next node and then the next after that. If either.next is in a cycle/loop, fast will go through that cycle/loop and slow will also edventually go through it too. They will eventually converge without us needing to know how long the linked list is. Since the problem statement restricts the max is 1000, you can simply keep a count and exit once the limit is reached. Which is computationally more efficient. The slow and fast counter is the best way if we don't know the size restrictions.
Count tracker example:
static boolean hasCycle(SinglyLinkedListNode head) {
// since the list size limit is 1000, you can change this based on your max limitations in specific use cases
int maxSize = 1000;
int count = 0;
while(head!=null) {
head = head.next;
count++; //if cycle exists count will increase forever in this while loop
if(count>maxSize){ //to stop our loop from running forever have a max contition check
return true;
}
}
return false;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Cycle Detection
You are viewing a single comment's thread. Return to all comments →
I think your confusion is like mine in at first assuming that the fast node is skipping a node while it is going "twice as fast". In reality it is not as
fast.next.next
is actually referencing the next node and then the next after that. If either.next
is in a cycle/loop, fast will go through that cycle/loop and slow will also edventually go through it too. They will eventually converge without us needing to know how long the linked list is. Since the problem statement restricts the max is 1000, you can simply keep a count and exit once the limit is reached. Which is computationally more efficient. The slow and fast counter is the best way if we don't know the size restrictions.Count tracker example:
static boolean hasCycle(SinglyLinkedListNode head) { // since the list size limit is 1000, you can change this based on your max limitations in specific use cases int maxSize = 1000; int count = 0; while(head!=null) { head = head.next; count++; //if cycle exists count will increase forever in this while loop if(count>maxSize){ //to stop our loop from running forever have a max contition check return true; } } return false; }