Algorithm:
- Have 2 pointers *fast and *slow.
- Increment fast twice as fast as slow.
- If there is a loop, sooner or later fast will catch slow.
#define TRUE 1
#define FALSE 0
int main() {
NODE *head = /* given list*/, *fast = head, *slow = head;
int is_looped = FALSE;
while( fast && (fast = fast->next) && (fast = fast->next) ) {
if( slow == fast ) {
is_looped = TRUE;
break;
}
slow = slow->next;
}
// is_looped is true if there is a loop
}
No comments :
Post a Comment