Friday, January 21, 2011

Find loop in linked list

Algorithm:

  1. Have 2 pointers *fast and *slow.
  2. Increment fast twice as fast as slow. 
  3. If there is a loop, sooner or later fast will catch slow. 



#define TRUE 1
#define FALSE 0

int main() {
    NODE *head = /* given list*/, *fast = head, *slow = head;
    int is_looped = FALSE;

    while( fast && (fast = fast->next) && (fast = fast->next) ) {
        
        if( slow == fast ) {
            is_looped = TRUE;
            break;
        }
        slow = slow->next;        
    }
    // is_looped is true if there is a loop           
}

No comments :

Post a Comment