jainpratik0911
BAN USERIn the question I am assuming the linked list ends after the loop completes.
- jainpratik0911 October 04, 2011Yeah you correct. This is how i corrected my mistake. Tell me if this can work.
loop(List)
{
p1 and p2 are two pointers;
Initially p1 points to start of the list;
p2=p1.next;
int c=1;
while(check(p1,p2,c) and p2!=p1)
{ p2=p2.next;c++; }
/* p2!=p1 will see if loop starts at very 1st node and check function will check loop that starts at other than 1st node */
// p2 points to node where loop starts
}
check(p3,p4,c)
{
int d=1;
while(p3.next!=p4)
{ p3=p3.next;d++; }
if(c==d) return true;
else
if(d<c) return false;
/* when d id less than c, that means now for travelling from p3 to p4 took lesser traversals than for p2 traversing. That will happen incase of a loop. */
}
}
Okay i thought he had told you no of elements.. Anyways its not even required to find the no of elements. Since it is given that there is only one loop here.
i can write the same as,
loop(List)
{
p1 and p2 are two pointers;
Initially p1 points to start of the list;
while(true)
{
p2=p1;
while(p2!= null and p2!=p1)
p2=p2.next;
if(p2==p1) break; //node where loop starts and hence i break from loop since there is only one loop here
p1=p1.next;
}
}
i answered il use a trie data structure to store words with the counts..
the node in structure will have a character name,a pointer and a variable count..
ill traverse through the book character by character...in the trie structure from the root node i keep moving towards the corresponding character....when in the book character is a \t (i.e a space) in the structure the last character nodes counter will be incremented...so in the end what the strucutre will have is for any node's count will give the count of the word which is denoted by characters from root node to that node....
so once structure created traverse the tree and find max count and traverse again from root to get that word...
please post for alternative nd better solutions
yeah that one's better :)
- jainpratik0911 October 04, 2011