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.
The 'slow' pointer never traverses the list more than once if you solve using the 'tortoise and hare' method. The worst case (entire list is traversed once) occurs when the cycle starts at the header node.
You see, since the number of nodes between the 'slow' and the 'fast' pointer decreases by 1 every iteration (in a cycle), once the 'slow' pointer reaches the first node of the cycle, it has to traverse only as many more nodes as the number between the two pointers before they meet(Remember, the number is counted starting from the 'fast' node, and in the direction it's travelling (clockwise/anticlockwise)).
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 →
The 'slow' pointer never traverses the list more than once if you solve using the 'tortoise and hare' method. The worst case (entire list is traversed once) occurs when the cycle starts at the header node.
You see, since the number of nodes between the 'slow' and the 'fast' pointer decreases by 1 every iteration (in a cycle), once the 'slow' pointer reaches the first node of the cycle, it has to traverse only as many more nodes as the number between the two pointers before they meet(Remember, the number is counted starting from the 'fast' node, and in the direction it's travelling (clockwise/anticlockwise)).