Fog Creek Software
Discussion Board




linked list

for the cycle detection cycle,I understood the answer but removal of a cycle in linked list does not make sense to me.If one of the links in a node points back to a previous node then there is no way I can say what it should have pointed to in the first place.

prat
Sunday, December 01, 2002

I think the point of the exercise is to detect that the linked list is invalid. A program trying to iterate will never complete. This is what you are testing for - what the list should have been is undeducible.

Paul Viney
Monday, December 02, 2002

I think 'break the loop' means to find the link that points back to a previous link and make the list end there, thus converting it to an unlooped list with the same elements in the same order.

David Clayworth
Thursday, December 12, 2002

Hmmm.  I must have missed something.

Surely it is quickest and easiest to detect a loop by storing the current pointer and then interating through the list - if for any subsequent item, the pointer to the next item is the same as the one you started at there is a loop, otherwise if you reach the end, there is no loop.  This way you have to check at most 'n' pointers in a list with 'n' items.

Iterating two pointers one twice as fast as the other you may have to check 2n pointers before you finish.

roo
Thursday, January 09, 2003

*  Recent Topics

*  Fog Creek Home