Difference between revisions of "TADM2E 3.27"
From Algorithm Wiki
(Blanked the page) |
|||
| Line 1: | Line 1: | ||
| + | <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; | ||
| + | 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. | ||
| + | </pre> | ||
| + | --[[User:Max|Max]] 06:18, 25 June 2010 (EDT) | ||
Latest revision as of 15:53, 23 July 2020
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)
