Saturday, October 15, 2005

answer to linked list problem

The answer is that you start both pointers at the head of the list and you move them both down it but you move the second pointer (call it B) twice as fast as you move pointer A. If there is a cycle, you'll eventually detect it. Set A to head if list. Set B to A->next. If B->next = A, you have already detected a cycle. Otherwise, advance B one node and compare to A again. Now advance A one node. Advance B two nodes, comparing to A each time.

No comments: