在双向链表中进行循环

Question

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

- Jony

---

这是一个常见的面试问题。以下是最优解的详细解释。 - Asaph

Answer 1

看到之前的答案和评论，我发现他们使用了与单链表检测循环相同的方法。但是，有一种更好的方法可以解决双向链表的问题。
这是我的方法-
检测循环
在双向链表中，当迭代时，我们维护一个节点 - “last”，表示当前节点之前的最后访问节点。如果任何节点存在循环，则对于该节点，“previous”指针（指向前一个节点的指针）将不同于“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;
} 

- abhishek gupta

Answer 2

将其视为单向链表，并执行以下操作。

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

在上面的代码中，我们使用了两个指针，一个是慢指针，另一个是快指针，慢指针每次移动一步，快指针每次移动两步。当它们相遇的时候，我们可以说链表中存在循环，否则不存在。

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

检测到循环后，我们可以使用一个循环，从开头开始，并像往常一样以其正常速度移动慢指针，当两个指针相遇时，会议点是循环的起点，我们可以打破它。

- Anuj Garg