Linked List: Detect a Cycle in a linked list – Two Pointers Approach (Faster)

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions

Sol 4: Two pointer approach (Faster)

In the last post we discussed about the regular two pointer approach and a bit about its background. Lets look into how we can make it a bit faster.

What can you do here to make it faster. In the regular approach, the faster pointer goes 2 nodes at a time and the slower pointer goes 1 node per iteration. You cannot really change the speed of the slower pointer, because you definitely need to check every node at least once. But what about the fast pointer? Why just have it go 2 nodes per iteration? Why not 3 or more? And what improvements can you get here? Well. the faster it goes the lesser, the number of assigments and null checks when you traverse the faster pointer. This will be helpful, especially when the cycle (loop) is large. But how can fast do can you go. Since you don’t really know, you could do an exponential advancement. What this means is that, start with 2 nodes per iteration, and see if the slower pointer meets it. If not, traverse 4 nodes in the next iteration, and then 8, 16, 32…

Here’s some sample code that illustrates this.

void LinkedList::IsLooped2() { 
    LNode* first=head; 
    LNode* second=head;
int i=0; 
int k=1; 
while(first) { 
    first=first->next; 
    i++; 
    if(second==first) { 
            cout < < "Found Loopn"; 
            return; 
    } 
    if(i==k) { 
        second=first; 
        k*=2; 
    } 
} 

}