Did any one find removing the loop in On time????
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.
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...
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.
Thursday, June 23, 2005
You have either misunderstood the problem or misinterpreted the solution for cycle detection?
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????
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.
Friday, June 24, 2005
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?
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
8,4 <-- match found with difference of 4
Phase 2: run iterator with difference of 4 to find first cycle
Phase 3: run iterator from 3 to 7 and set pointer to null if it points to 3.
Monday, June 27, 2005
Fog Creek Home