3.43

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
1) Take two pointers Fast and Slow (Slow jumps one step at a time while Fast two step)
2) While (Fast != NULL)
        if(Fast == Slow)
              return true;
        else
             fast = fast->next->next
             slow = slow->next
3) return false;
After detecting loop stop one pointer and increment other pointer by 1 step untill
Loop
    if (fast == slow)
    break;
else
    slow++
    LoopLength++
EndLoop

You can find out loop start position also.
Once you have LoopLenght.

1. Fast = Slow = Start
2. Fast += LoopLenght
3. Loop
    If Fast != Slow
    Fast++;
    Slow++
EndLoop
4. Fast and Slow Both are pointing to the start of loop position. Now you can break the Loop in link list.

--Max 06:18, 25 June 2010 (EDT)


Back to Chapter 3