Adobe Interview Question
Country: United States
Use Floyd's Cycle Finding Algorithm
int isListCircular(ListNode* head){
if(head==NULL)
return 0;
ListNode *fast=head, *slow=head;
while(fast && fast->next){
if(fast->next->next==slow)
return 1;
fast=fast->next->next;
slow=slow->next;
}
return 0;
}
#include<stdio.h>
typedef struct node_s {
void *data;
struct node_s *next;
} NODE;
int list_has_cycle(NODE *list)
{
NODE *fast=list;
while(1) {
if(!(fast=fast->next)) return 0;
if(fast==list) return 1;
if(!(fast=fast->next)) return 0;
if(fast==list) return 1;
list=list->next;
}
return 0;
}
int main()
{
NODE n1, n2, n3, n4, n5;
n1.next=&n2;
n2.next=&n3;
n3.next=&n4;
n4.next=&n5;
n5.next=NULL;
printf("Test without cycle: ");
if(list_has_cycle(&n1)) printf("cycle\n");
else printf("no cycle\n");
n5.next=&n3;
printf("Test with cycle: ");
if(list_has_cycle(&n1)) printf("cycle\n");
else printf("no cycle\n");
return 0;
}
check this ..
- sekar April 08, 2013codingskills4u.com/2013/01/find-loop-in-linked-list.html