Saturday, February 5, 2011

Find loop in a linked list

 



We have to maintain two pointers one slow pointer that moves one node at a time and a fast pointer that moves two nodes at  a time.



#include <stdio.h>
#include <stdlib.h>

struct linkedList{
    int number;
    struct linkedList* next;
};

typedef struct linkedList* NODE;

int FindLoop(NODE *head)
{
    NODE *fastPtr, *slowPtr;
    fastPtr = slowPtr = head;
    while(1)
    {
        if(!fastPtr || !fastPtr->next)
            return 0;
        else if(fastPtr == slowPtr || fastPtr ->next == slowPtr)
            return 1; // Loop Exist
        else{
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }
    }
    return 0;
}