Write an algorithm to detect a corrupt node in a linked list, i.e
There is a linked list. The last node could point back to any node in
the list (including the head). Find the node in the list to which the
last node points. Or in other words at which node does the circular
linked list start.
Answer:
Solution 1 : O(n) solution, ( This is the most expected solution )
#include "iostream"
#include "stdio.h"
using namespace std;
struct Node
{
int val;
Node *next;
Node(int _val, Node* _next=0):val(_val),next(_next){}
};
Node* createLinkedListWithLoop(size_t n)
{
Node *head = 0;
Node *prev = 0;
Node *last = 0;
printf("\n ---- \n");
for ( int i = 0; i < n; ++i)
{
head = new Node(0,prev);
printf("\n New Node %#x \n", head);
prev = head;
if ( !last ) last = head;
}
head = prev;
// create the loop
last->next = head->next->next->next->next;
printf("\n The last node points to %#x \n", last->next);
return head;
}
size_t countElements(Node* list, const Node* delim_node)
{
size_t count = 0;
while(list != delim_node)
{
++count;
list = list->next;
}
return count;
}
void findLoop(Node* list)
{
// step 1 : Find a node that occurs in the loop
// this is done by taking two pointers and traversing
// the linked list such that :
// PtrA moves at steps of 1
// PtrB moves at steps of 2,
// so that they will intersect each other in the loop.
Node * listA = list;
Node * listB = list;
do
{
if ( listA )
listA = listA->next;
// increment twice
if ( listB )
listB = listB->next->next;
}while(listA != listB);
// now treat list to listA as one list
// and treat listB->next to listA as another list
// i.e. find the point of intersection of these two lists
// and during the traversal, the second node pointing to this
// intersection is the corrupt node.
// the point of intersection
const Node* delim_node = listA;
// the first sub linked list
listA = list;
// the second sub linked list
listB = listB->next;
// step 2 : count the elements
size_t countA = countElements(listA, delim_node);
size_t countB = countElements(listB, delim_node);
// step 3 : align the ptrs so that they are
// at the same distance from the end
while (countA != countB)
{
if( countA > countB )
{
--countA;
listA = listA->next;
}
else
{
--countB;
listB = listB->next;
}
}
// step 4 : move both the ptrs one at a time, and check if they
// both point to same node.
Node *corrupt_node = 0;
while( listA != listB )
{
listA = listA->next;
corrupt_node = listB;
listB = listB->next;
}
// we have found the intersection now,
printf("\n Intersection at %#x, corrupt node %#x \n",
listA, corrupt_node);
}
int main()
{
Node* list = createLinkedListWithLoop(16);
findLoop(list );
return 0;
}
Solution 2 : O(n) time, O(n) space solution, but single pass.
Take a hash_map, as we traverse the linked list,
if ( node ) is absent in hash_map, add it
else if the node is present, then we have found a loop.
