Find start of loop in linked list
Find the start of a loop in a linked list (if it exists). Only the head of the linked list is provided.
/*
* StartOfLoop.cpp
*
* Created on: Apr 18, 2012
* Author: Kiran Hegde
*/
#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
struct Node {
int data;
Node *next;
};
/**
* Generate a linked list of size containing random numbers from 0 to 9
*/
Node *createCircularLinkedList(int totalSize, int loopSize) {
srand(time(NULL));
Node *head = NULL;
Node *last = NULL;
for (int i = 0; i < totalSize; i++) {
Node *node = new Node;
node->data = rand() % totalSize; //random numbers from 0 to totalSize-1
node->next = head;
head = node;
if (i == 0) {
last = node;
}
}
// get node that is loopSize from end
if (loopSize > 0) {
Node *p = head;
int count = 0;
while (count < totalSize - loopSize) {
p = p->next;
count ++;
}
//point the last node to the above node to create the loop
last->next = p;
}
return head;
}
void deleteCircularLinkedList(Node *head, int size) {
int count = 0;
while ((head != NULL) && (count < size)) {
Node *temp = head;
head = head->next;
delete temp;
count++;
}
}
void printCircularLinkedList(Node *head, int totalSize, int loopSize) {
Node *curr = head;
int count = 0;
while ((curr != NULL) && (count <= totalSize)) {
cout << curr->data;
curr = curr->next;
if ((count == totalSize) || (count == (totalSize - loopSize)))
cout << "*";
if (count < totalSize)
cout << "-->" ;
count++;
}
if (curr == NULL)
cout << "EMPTY" << endl;
else
cout << endl;
}
/**
* Return true if there is a circular loop in a linked list
*/
bool containsLoop(Node *head) {
Node *slow = head;
Node *fast = head;
bool isLoop = false;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast) {
isLoop = true;
break;
}
}
return isLoop;
}
/**
* This is a popular solution based on creating fast and slow runners that
* traverse the linked list. fast runner traverses twice as fast as slow.
* If head is "N" nodes before the start of the loop, by the time slow
* runner reaches the start of loop, fast runner would have traversed
* N nodes into the loop. Basically, the fast runner would be (loopSize - N)
* behind slow runner at this point. When the two meet, they will be N
* nodes before the start of the loop. After the two meet, move one of
* the runners back to the head. Now, traverse till the two meet again.
* This will give us the beginning of loop.
*/
Node *findStartOfLoop(Node *head) {
Node *slow = head;
Node *fast = head;
bool isLoop = false;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast) {
isLoop = true;
break;
}
}
if (!isLoop)
return NULL;
//Move fast pointer to head
fast = head;
//Move both pointers one step at a time till they meet
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
/**
* Test the code
*/
int main() {
Node *head = createCircularLinkedList(50, 10);
cout << "The List: ";
printCircularLinkedList(head, 50, 10);
bool loop = containsLoop(head);
cout << "Linked List Contains Loop: " <<
(loop ? "Yes" : "No") << endl;
if (loop) {
Node *node = findStartOfLoop(head);
cout << "The loop is at Node with value: " << node->data << endl;
}
deleteCircularLinkedList(head, 50);
return 0;
}