Fog Creek Software
Discussion Board




linked list

Did any one find removing the loop in On time????

Deepak Pant
Saturday, June 18, 2005

Run two iterators where the fastest moves at twice the speed of the slowest. If the two iterators are on the same element, you have a cycle.

WanFactory
Monday, June 20, 2005

The fun is - he said "remove", not "detect", and this is a different problem, which may not fall in O(n) time...

DK
Wednesday, June 22, 2005

I think Removal of loop can also be done in O(n) and same algo which detects loop can be used. There will be single change at the end. When we will come to end ie. when both iterators point to same element then change next pointer of any one iterator to NULL. This will remove the Loop.

Sudesh Chandna
Thursday, June 23, 2005

Sudesh Chandna,
You have either misunderstood the problem or misinterpreted the solution for cycle detection?

let say
you have the following link list


1--> 2--> 3--> 4--> 5 (connected back to 3)....

Now if you solve it by increamenting one pointer with x speed and the other with 2*x it is not necessary that they will be equal when they are pointing to 5 (loop construct!!!!)........
As in this case they will be equal when they are pointing to  4. So can you just make the next of 4 null????

Deepak pant(STM)
Thursday, June 23, 2005

I think you can fix that by running the iterators backwards at the same speed until the equality breaks. That will identify earliest manifestation of the cycle and allow a cut at the end.

WanFactory
Friday, June 24, 2005

WanFactory,
I think you will not achive the solution
"by running the iterators backwards at the same speed until the equality breaks."

Consider the list like this
1--> 2--> 3--> 4--> 5-->6 (connected back to 3)
In this case when equality meets both the pointers will be pointing to 3.
If you back iterate both pointers untill the equality break (which will definitely break by one movement back of both the pointers) the pointer will be pointing  to 2 and 5 neither of which are responisble of creating the loop.????

ALSO YOU CANT BACK ITERATE IN THE SINGLE LINK LIST....
IT HAVE ONLY ONE WAY CONNECTION?

Deepak pant(STM)
Saturday, June 25, 2005

if you have 1, 2, 3, 4, 5, 6, 3, ...
then basically you are saying 3=7, 4=8, 5=9, .

Phase 1: run iterators at differing speed
1,1
2,1
3,2
4,2
5,3
6,3
7,4
8,4 <-- match found with difference of 4

Phase 2: run iterator with difference of 4 to find first cycle
1,5
2,6
3,7

Phase 3: run iterator from 3 to 7 and set pointer to null if it points to 3.

WanFactory
Monday, June 27, 2005

*  Recent Topics

*  Fog Creek Home