Motorola Interview Question
Software Engineer / DevelopersWhat if you had no control at the time of the list creation?
this wont work,...
I have a solution based on the hash map, but that handles only 1 type of mal pointer out of 2 possible cases,
The solution below solves the case when there is a loop in list...
1-2-3 4-5-6-null, 3 points to 1
start traversing the list and make a hash map as below and look for collision if there is a collision then there is a bad pointer
1 Null
2 1
3 2
now comes 1 again and collision occurs...
But another case:
1-2-3 4-5-6-null, 3 points to 5
is not solvable here as we do not have a reference to 4...
there may be a loop in there !!
so we also have to check for its existence first
then above method would work..
private static void printLoopLocation(Node node)
{
boolean isLoop = false;
Node slow;
Node fast;
int count=0;
slow = fast = node;
while(true)
{
slow = slow.getNext();
fast = fast.getNext().getNext();
if(slow == null || fast == null)
{
System.out.println("There is no loop in the list.");
break;
}
if(slow == fast)
{
System.out.println("There is a loop in the list.");
isLoop = true;
break;
}
}
if(isLoop)
{
// Now count the number of nodes in the loop
slow = slow.getNext();
count++;
while(slow != fast)
{
slow = slow.getNext();
count++;
}
}
System.out.println("There are "+count+" nodes in the loop.");
// Now we will find the starting point of the loop
// Move both pointers to the start of the list
slow = fast = node;
for(int i=1;i<=count; i++)
{
fast = fast.getNext();
}
// Now fast pointer is count nodes away from the slow pointer
// Increment both pointers one by one until they meet. Meeting point is the place where loop starts.
while(slow != fast)
{
slow = slow.getNext();
fast = fast.getNext();
}
System.out.println("The loop starts at "+ slow.getData());
}
Keep a count of the total number of nodes in the linked list i.e every time you add a node increment the count.
- Anonymous June 26, 2011So if there is a random pointer in the linked list then the total number of nodes will be less than the count that you have maintained.Because the nodes between the random pointer and the node to which it is pointing can never be accessed.