Detect loop in linked list and start of loop

Detect loop in linked list

Given a singly linked list, which may or may not contain a loop in it,detect loop in linked list and it yes, start of the loop should be returned. For example, in following linked list, function should return yes for detecting if there is loop in linked list and N3 as start of that loop.

detect loop in linked list
Linked list with loop

Methods to detect loop in linked list

Using visited flag 
In singly linked list, we can traverse only in one direction and end of the list is detected when NULL pointer is encountered. What if linked list has a loop in it? Then we would never reach end of the list and circle around in the loop. When we circle around in a linked list, node which was visited earlier will be visited again. How can we remember that we have already visited node? Yes, we can mark node as visited when we visit it. At every node, before traversing further, check if visited flag is true, if yes, then linked list has a loop.

There is a drawback of this method because we need to change internals of node representation of linked list in order to add visited flag. This also leads to extra space usage in tune of O(n). However algorithm and implementation is very simple.

Using hash table
In above method, modification in nodes of linked list is done to store visited flag. To avoid that, we can maintain a hash table. Whenever a node is visited, check if node is already present in hash, if yes, then there is a loop. If linked list is completely traversed without any collision in hash, then there is no loop. Usual question asked by interviewers here is that what should be key of hash? If answer is the data in the node, next question follows is will that work for a linked list with duplicate numbers. So correct answer for above question is that node’s address should be the key and not the value. There is another data structure which provided by high level languages called as set. In this case, set is best because of it’s property that it does not allow to add duplicate elements in it. If insertion in set fails, we know that we have already added that node and hence there is a loop and the node at which first collision happens is start of loop.
Good approach, however, it requires O(n) extra space.

Using Flyod’s algorithm. (also known as Hare and Tortoise algorithm)
Basic principle of this algorithm is that if two pointers are moved at different speed to traverse a linked list, these two pointers will surely meet at a node which in the loop, if there is a loop in list.
Take two pointers, first which moves one node at a time, let it be slow; other which moves two nodes at a time, call it fast. If slow meets fast at any point of time, then there is a loop in linked list.
Traversal of two pointers in above list would be

Slow : 2 , Fast : 3
Slow : 3 , Fast : 5 
Slow : 4 , Fast : 3
Slow : 5 , Fast : 5

First problem is solved. If before reaching NULL, if slow meets fast, then there is a loop in list.

Why fast pointer moves only two nodes ahead and not three or any other number? This is because traversing more than two nodes at a times gives a window where slow and fast don’t meet in iteration and we might have to iterate more times. By having the fast pointer incremented by two  we guarantee that we’ll be maximizing your efficiency in the case of worst case scenario.

Second problem that is to find starting node of loop, requires some thinking.What would be the condition when slow meets fast? Can we have the length of the loop? Yes. Move the slow pointer till it again meets faster pointer and keep count of number of nodes. Let number of nodes in loop be K

Now the problem reduces to finding Kth node from the end because if there are K nodes in loop, start node of loop would be Kth node from the end of the list. Move one pointer K nodes ahead of head and keep other at head. Move both of them simultaneously. When they meet, that node is starting point of the loop.

Algorithm to detect loop in linked list

Cycle detection

1. Take two pointers, slow and fast and initialize to head
2. Move them at different speed,slow one step and fast two steps at a   time
3. If slow and fast point meet before slow reaches NULL, there is a loop
4. Else return false

Starting node detection

1. Find length of loop in linked list (K) using the meeting point of fast and slow pointer found in above algorithm.
2. Once K is known, find Kth node from end in list and that will be start of loop

To read more , refer find nth node in linked list from end

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
        int data;
        struct node *next;
} Node;
 
Node * findLoop(Node *head){
 
  Node *slow = head;
  Node *fast = head;
  Node *ptr1;
  Node *ptr2;
  int k = 1, loopFound = 0, i;
 
  if(!head) return NULL;
 
  while(fast){
  	   /*Moving fast pointer two steps at a time */  
  	   fast = fast->next;
  	   if(fast)
  	   	fast = fast->next;
 
       slow = slow->next;
       if(slow == fast){
            loopFound = 1;
            break;
       }
   }
 
   if(loopFound){
   /* We have detected a loop */
   /*Let's count the number of nodes in this loop node */
    ptr1  = fast;
    while(ptr1 && ptr1->next != slow){
     	ptr1 = ptr1->next;
     	k++;
    }
 
   /* Now move the other pointer by K nodes */
    ptr2 = head;
    ptr1 = head;
    for(i=0; i<k; i++){
       ptr2 = ptr2->next;
    }
 
    /* Now if we move ptr1 and ptr2 with same speed 
     they will meet at start of loop */
    while(ptr1 != ptr2){
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return ptr1;                     
   }
   return NULL;
}

/* Addition of a node to linked list */
void push(Node **head, int value){
    if(*head == NULL){
        (*head) = (Node *)malloc(sizeof(Node));
        (*head)->data = value;
        (*head)->next = NULL;
    }
    else{
        Node * temp = (Node *)malloc(sizeof(Node));
        if(temp){
    	  	temp->data = value;
        	temp->next = (*head);
            *head = temp;
        }
    }
}
 
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        /* creating list */
        push(&L1,3);
        Node *lastNode = L1;
        push(&L1,4);
        push(&L1,6);
        Node *loopNode = L1;
        push(&L1,7);
        push(&L1,8);
        push(&L1,9);
        push(&L1,7);
        lastNode->next = loopNode;
 
        loopNode = findLoop(L1);   
        printf("Loop in list : %s", loopNode ? "true" :"false");
        printf("\nStart node : %d", loopNode ? loopNode->data : -1);
        return 0;
}

Detect loop in linked list : Test cases

Complexity of above algorithm to detect loop in linked list will be O(N).
Space complexity is O(1) when the memory required for an algorithm is independent of its input size. Here, only 2 pointers (fast and slow) are used, which is constant. Hence the space complexity is O(1).