Looping in a doubly linked list

Question

How to find a loop in a doubly linked list? How to eliminate cycles?

Answer 1

Consider this as a separate list and perform the following operations.

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 (slow_p == fast_p) { printf("Found Loop"); return 1; } } return 0; } 

In the above code, we use two pointers: one is slow and the other is fast, slow moves one step and quickly moves two steps at a time. The time when they both meet, we can say that the linked list has a loop, otherwise not.

 void removeLoop(struct node *loop_node, struct node *head) { struct node *ptr1; struct node *ptr2; /* Set a pointer to the beging of the Linked List and move it one by one to find the first node which is part of the Linked List */ ptr1 = head; while(1) { /* Now start a pointer from loop_node and check if it ever reaches ptr2 */ ptr2 = loop_node; while(ptr2->next != loop_node && ptr2->next != ptr1) { ptr2 = ptr2->next; } /* If ptr2 reahced ptr1 then there is a loop. So break the loop */ if(ptr2->next == ptr1) break; /* If ptr2 did't reach ptr1 then try the next node after ptr1 */ else ptr1 = ptr1->next; } /* After the end of loop ptr2 is the last node of the loop. So make next of ptr2 as NULL */ ptr2->next = NULL; } 

After detecting the cycle, we can use one cycle and start from the beginning and move the slow pointer to it, as usual, the speed when both pointers meet the meeting point is the beginning of the cycle, and we can break it.