Created
May 15, 2014 16:04
-
-
Save sundeepblue/845a1aa00b3c196d2b23 to your computer and use it in GitHub Desktop.
detect cycle in array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Given an array of integers where each element points to the index of the next element | |
how would you detect if there is a cycle in this array | |
Note: if the element of array is in range[0, n-1], where n is the length of array, then there must be at least one cycle. | |
Thus, the element may be negative or out of range[0,n-1] | |
/* | |
bool has_cycle_in_array(int a[], int N) { | |
if(N == 1) return false; | |
int slow = 0, fast = 0; | |
while(slow < N && fast < N) { | |
if(a[slow] >= 0 && a[slow] < N) | |
slow = a[slow]; | |
else { | |
slow++; | |
fast++; | |
continue; | |
} | |
int step = 0; | |
while(step < 2 && a[fast] >= 0 && a[fast] < N) { | |
fast = a[fast]; | |
step++; | |
} | |
if(step < 2) { | |
fast++; | |
slow = fast; | |
} else if(slow == fast} return ture; | |
} | |
return false; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
typo 1
Thus, the element may be negative or out of range[0,n-1]
*/
typo 2
} else if(slow == fast) return ture;