solution of second problem- "How do you remove a loop in a linked list with the same constraints?"
if n - num of list before loop
k - length of loop
x - place on loop where pointers met
we have 2n+2x = n+k+x or n+x=k
so if 1 pointer starts from begining of list and second from place n+x, they met in start/end of loop
Sergey N. Sokolov
Sunday, July 25, 2004
Can u please explain it with an example.
Sunday, August 22, 2004
Hi, the best answer to this Question which i think is more relevent is..
I assume you are clear with the reversion of linked list
1- Start Reversing the Link list
2- At one ponit where the loop starts in ur ur algo(if u r using the recursion). U will get the pointer returned by ur Sub revered list and the pointer current will be equal.
This way u can can get to know everything related to this problem. Number of nodes in loops, Where its happeing.and total number if before hand u dont know
Thursday, September 16, 2004
Fog Creek Home