3.43

From The Algorithm Design Manual Solution Wiki
Revision as of 18:16, 20 September 2020 by Algowikiadmin (talk | contribs) (Created page with "<pre> 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;...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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