WAP to Detect Loop In Doubly Linked List

Algorithm : Floyd’s Cycle-Finding Algorithm:
This is the fastest method. Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop. Apart from above case one more cases may arises.

Case 1 : Whole link list is in loop. It Means last node points to first node. This can be solved by using two pointers. one pointer points to given node in link list and another pointers loops around the link list
If (Given_node == node->next) or or if(fast->prev=slow->prev)  Explained Above

Case 2: Part of link list is in loop
If (node->next != node->next->next->prev) is true means double link list is a loop.

 Time Complexity Will be O(N) N is length of Linked List




#include
#include

struct node
{
int data;
struct node *next;
struct node *prev;
};

int detectLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while(slow_p && fast_p &&
fast_p->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (fast_p->prev==slow_p->prev|| slow_p == fast_p) //Look Closely !!!!!!!!!!!!!!!
{
printf("Found Loop");
return 1;
}

}
return 0;
}

void push(struct node** head_ref, int new_data)
{
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

new_node->data = new_data;

prev is always NULL */
new_node->prev = NULL;

new_node->next = (*head_ref);

if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

(*head_ref) = new_node;
}

void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

int main()
{
/* Start with the empty list */
struct node* head = NULL;

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);

printf("\n Original Doubly Linked list ");
printList(head);

//head->next->next->next=head->next; //1st test case
// head->next=head;//2nd test case //head->prev=head not necessary
head->next->next->prev=head;// 3rd Test Case
/* similarly we can do it using prev pointer for this we have to go to last node first the
start form its prev pointer .. so making the loop in program is our choice it depnds how we
connects them using prev & next pointer */

detectLoop(head);


//printf("\n After Looping Doubly Linked list ");
//printList(head); //Testing Purpose Only

getchar();
}

TC O(n)
SC O(1)
Run Here https://ideone.com/r4aZW