Loop in a link list!

[Manish K]

Hi  :

We all know the problem i.e to find a loop in a linklist.

Known Solution is : take two pointer , move 1st pointer by 1 poistion and 2nd pointer by 2 position whenever both point to the same node there is a loop.

But if i would move 1st pointer by m position and 2nd pointer by n position then what would be the relation between m and n s.t we would be able to find the loop.

Thanks

Manish

[srinivasarao javvadi]

Hi Manish,

  You can consider the looping by following way:

Two cars are rotating in a circle with different speeds. ( No matter what the speed is ). Definitely they will meet at some point in the circle.

Coming to pointer increments also same. You can take any number which represents an increment. Only thing you need to check is .... incrementing that many Node->next is valid or not   ( If loop is not existed ) 

-Srinivas  

--
Visit http://www.gowrikumar.com for good puzzles in C programming language and programming interview questions.
 
You received this message because you are subscribed to the Google Groups "Programming Puzzles" group. To post to this group, send email to programmi...@googlegroups.com

--
Srinivas

[Nishant Agarwal]

GCD of m and n should be 1

.... :-)
*****************************************
Nishant Agarwal
Computer Science and Engineering
NIT Allahabad
*****************************************

[Dileep Vaka]

Solution #1
Two pointers as mentioned by Srinivas

Solution #2
Try reversing the linked list . If the starting node of the original and the reversed list are same implies a presence of loop in linked list.

--
Dileep Vaka
www.dileep.com

[Albert]

@dileep:


in your second solution you cant reverse a link list if there is a
loop .....
there is no end for the list to get reversed....
just try it tell me if i am wrong....

[srinivasarao javvadi]

Solution 2) is correct. If you have a diagrammatic representation for reversing the linked list , then probably you can get how it works. 

-Srinivas 

--
Visit http://www.gowrikumar.com for good puzzles in C programming language and programming interview questions.

You received this message because you are subscribed to the Google Groups "Programming Puzzles" group. To post to this group, send email to programmi...@googlegroups.com

--
Srinivas

[Manish K]

Guys ,

I know the solution of finding a loop in a link list but i am looking for a general solution for two pointer approach.

Thanks

Manish

[Fazlur Rahman Naik]

Probably you guys can go through the link, with a detailed explanation and the implementation.

http://commoninterview.com/Programming_Interview_Questions/test-for-cycle-in-a-single-linked-list/

Regards,
Fazlur.

[neeraj]

hi manish,
for 1st by M position and 2nd by N position

first calculate LCM(M,N)=L(say) now these two pointers can only meet
at a*L for (a=1,2,3,4........)
these positions,
if the above two pointers at these (a*L ) positions at the same
time point to the same node then loop exist else not.

OBVIOUSLY, we continously monitor that node->next is valid or not..


-neeraj