Difference between revisions of "TADM2E 3.27"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
 
Line 1: Line 1:
<pre>
+
<pre>
 
1) Take two pointers Fast and Slow (Slow jumps one step at a time while Fast two step)
 
1) Take two pointers Fast and Slow (Slow jumps one step at a time while Fast two step)
 
2) While (Fast != NULL)
 
2) While (Fast != NULL)
Line 5: Line 5:
 
               return true;
 
               return true;
 
         else
 
         else
             fast = fast-&gt;next-&gt;next
+
             fast = fast->next->next
             slow = slow-&gt;next
+
             slow = slow->next
 
3) return false;
 
3) return false;
 
After detecting loop stop one pointer and increment other pointer by 1 step untill
 
After detecting loop stop one pointer and increment other pointer by 1 step untill
Line 28: Line 28:
 
EndLoop
 
EndLoop
 
4. Fast and Slow Both are pointing to the start of loop position. Now you can break the Loop in link list.
 
4. Fast and Slow Both are pointing to the start of loop position. Now you can break the Loop in link list.
&lt;/pre&gt;
+
</pre>
 
--[[User:Max|Max]] 06:18, 25 June 2010 (EDT)
 
--[[User:Max|Max]] 06:18, 25 June 2010 (EDT)

Latest revision as of 18:22, 11 September 2014

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)