The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Linked List

Problem :-
Detect a loop in a given linked list.
Due to some bug, a node may contain a link to some previous node in the linked list. This creates an loop which would lead to a program hang while traversing the list.
Give an algorithmic approach to detect a loop if it exits.

Solution :-
This is a standard interview question with a very simple solution.
Maintain two pointers, slow pointer which iterates over each node in the list & fast pointer which takes two steps at a time i.e skips every alternate node. If at any point of time slow & fast pointers intersect, then there is a loop in the list.

#include<iostream>
using namespace std;

// list node structure
typedef struct list_node {
   int data;
   struct list_node *next;
}node;

// create new node
node *getNewNode(int data) {
   node *new_node = new node;
   new_node->data = data;
   new_node->next = NULL;
   return new_node;
}


// append a node to the list
void addNodeToList(node **head, int data) {
   if (*head == NULL)
      *head = getNewNode(data);
   else {
      node *ptr = *head;
      while (ptr->next != NULL)
         ptr = ptr->next;
      ptr->next = getNewNode(data);
   }
}

// create a list
node *createList() {
   node *head = NULL;
   addNodeToList(&head,12);
   addNodeToList(&head,7);
   addNodeToList(&head,11);
   addNodeToList(&head,19);
   addNodeToList(&head,9);
   addNodeToList(&head,99);
   addNodeToList(&head,18);
   addNodeToList(&head,76);
   addNodeToList(&head,32);
   addNodeToList(&head,49);
   addNodeToList(&head,3);
   addNodeToList(&head,66);
   // create a loop for testing
   node *ptr = head;
   while (ptr->next != NULL)
      ptr++;
   node *temp = head->next->next->next;
   ptr->next = temp;
   return head;
}

// traverse the list
void traverseList(node *head) {
   node *ptr = head;
   while (ptr != NULL) {
      cout<<ptr->data<<" ";
      ptr = ptr->next;
   }
}

// Detect a loop in the list
bool detectLoop(node *head) {
   node *slow, *fast;
   slow = fast = head;
   while (slow && fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
      if (slow == fast)
         return true;
   }
   return false;
}

// main
int main() {
   node *head = createList();
   bool loop_present = detectLoop(head);
   if (loop_present) {
      cout<<"\nLoop detected in the list";
   }
   else
      cout<<"\nNo loop present";
   cout<<endl;
   return 0;
}

Back | Next

All problems on Linked List
* Insert, Delete and Search nodes in a single linked list
* Insert, Delete and Search nodes in a double linked list
* Sort a linked list where each node element is either 1 or 0
* Reverse a linked list in an efficient manner
* Merge two sorted linked lists
* Detect a loop in a given linked list