linked-list - 在双向链表中循环

Question

如何在双向链表中找到循环？如何消除循环？

Answer 1

查看对这个问题的上一个答案和评论，我看到他们使用与用于检测单链表中的循环相同的方法。但是，对于双向链表，有一个更好的方法来解决这个问题。
这是我的方法-
检测环路
在双向链表中，在迭代时我们维护一个节点 - “last”代表在当前节点之前最后访问的节点。如果在任何节点存在循环，那么对于该节点，“前一个”指针(指向前一个节点的指针)将与“最后一个”节点不同。
另一方面，如果没有循环，我们将到达终点。

去除环路
我们只是将“last”的“next”更新为不指向任何内容(C++ 中为 NULL)。

这是我的 C++ 实现:

#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;
}