looping in a doubly linked list

Question

how to find a loop in a doubly linked list??how to eliminate the loops?

Answer 1

Looking at the previous answer and comment to this problem, I see that they use the same approach that is used for detecting the loop in a singly-linked-list. But, there is a better way to solve this for a doubly linked-list.
Here is my approach-
Detecting the Loop
In a Doubly linked-list ,while iterating we maintain a node - "last" representing the last visited node just before the current one. If there is a loop at any node then for that node the "previous" pointer( pointer to the previous node) will not same as "last" node.
On the other hand if there is no loop we will reach the end.

Removing the Loop
We simply update the 'next' of "last" to point to nothing ( NULL in C++).

Here is my C++ implementation:

#include <iostream>
using namespace std;
struct node{
    int val;
    node *next=NULL,*prev=NULL;
    node(int x):val(x){}
};
bool detectAndRemoveLoopInDLL(node* head){
    node* last = NULL;
    while(head){
        if(last && last!=head->prev){
            cout<<"Loop found at: "<<head->val<<endl;
            last->next = NULL;
            return true;
        }
        last = head;
        head = head->next;
    }
    cout<<"No loop found"<<endl;
    return false;
}
int main() {
    node* head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3); head->next->prev = head;
    head->next->next->next = new node(4); head->next->next->prev = head->next;
    head->next->next->next->next = new node(5); head->next->next->next->prev = head->next->next;
    head->next->next->next->next->next = new node(6); head->next->next->next->next->prev = head->next->next->next;
    head->next->next->next->next->next->next = new node(7); head->next->next->next->next->next->prev = head->next->next->next->next;
    head->next->next->next->next->next->next->next = new node(8); head->next->next->next->next->next->next->prev = head->next->next->next->next->next;
    //comment this for no loop
    head->next->next->next->next->next->next->next->next = head->next->next;
    head->next->next->next->next->next->next->next->prev = head->next->next->next->next->next->next;
    detectAndRemoveLoopInDLL(head);
    return 0;
}