Linked List

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.

Sundar Rajan.G.S
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 

neelesh
Thursday, September 16, 2004

  Recent Topics

  Fog Creek Home