Detect Loop in a Linked List (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;
    }
}

}

This is based on Richard Brents Algorithm . Other Operations on this *** Refer for removing the loop and other functionalities on this link .

CODE

/* Function to remove loop. Used by detectAndRemoveLoop() */
void removeLoop(struct node *, struct node *);

/* This function detects and removes loop in the list
  If loop was there in the list then it returns 1,
  otherwise returns 0 */
int detectAndRemoveLoop(struct node *list)
{
    struct node  *slow_p = list, *fast_p = list;

    while (slow_p && fast_p && fast_p->next)
    {
        slow_p = slow_p->next;
        fast_p  = fast_p->next->next;

        /* If slow_p and fast_p meet at some point then there
           is a loop */
        if (slow_p == fast_p)
        {
            removeLoop(slow_p, list);

            /* Return 1 to indicate that loop is found */
            return 1;
        }
    }

    /* Return 0 to indeciate that ther is no loop*/
    return 0;
}

 How to Remove the loop 
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

 
/* Function to remove loop.
 loop_node --> Pointer to one of the loop nodes
 head -->  Pointer to the start node of the linked list */
void removeLoop(struct node *loop_node, struct node *head)
{
    struct node *ptr1 = loop_node;
    struct node *ptr2 = loop_node;
 
    // Count the number of nodes in loop
    unsigned int k = 1, i;
    while (ptr1->next != ptr2)
    {
        ptr1 = ptr1->next;
        k++;
    }
 
    // Fix one pointer to head
    ptr1 = head;
 
    // And the other pointer to k nodes after head
    ptr2 = head;
    for(i = 0; i < k; i++)
      ptr2 = ptr2->next;
 
    /*  Move both pointers at the same pace,
      they will meet at loop starting node */
    while(ptr2 != ptr1)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
 
    // Get pointer to the last node
    ptr2 = ptr2->next;
    while(ptr2->next != ptr1)
       ptr2 = ptr2->next;
 
    /* Set the next node of the loop ending node
      to fix the loop */
    ptr2->next = NULL;
}