Difference between revisions of "TADM2E 3.27"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
| − | + | <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- | + | fast = fast->next->next |
| − | slow = slow- | + | 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. | ||
| − | + | </pre> | |
--[[User:Max|Max]] 06:18, 25 June 2010 (EDT) | --[[User:Max|Max]] 06:18, 25 June 2010 (EDT) | ||
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)
