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.
/**boolean hasCycle(Node head) { if (head == null) return false; Metaphor,it is like clock,with 1 sec(slow) ,2 sec(fast),slow 1 2 3 4fast 2 4 6 8diff 59 58 57 56 **///The dynamic algorithm mainly want to enter the clock/** If a loop exists, then the fast pointer will eventually end up behind the slow pointer. The fast pointer will then catch up to the slow pointer, detecting the loop. This will always happen, no matter the size of the loop. Ability is the find the existence of loop,not the location of loop!!! **/booleanhasCycle(Nodehead){Nodeslow=head;Nodefast=head.next;while(slow!=fast){if(fast==null||fast.next==null)returnfalse;slow=slow.next;//the absolute distance between 2 node when looped is always reduce by onefast=fast.next.next;//The smart point is not a static check point(because it only check the static position!)}returntrue;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Linked Lists: Detect a Cycle
You are viewing a single comment's thread. Return to all comments →
I have a good analogy for this smart solution