循环在双向链表中

Question

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

Answer 1

将它看作是单链表并执行以下操作。

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

在我们使用了两个三分球一个是慢，另一个是快速的，上面的代码，移动速度慢一步，快速移动时，在他们都满足，我们可以说一个time.The时间两个步骤的链表有循环，否则不是。

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

检测循环后，我们可以使用一个循环，从头开始，并在移动缓慢的指针，和往常一样的速度，当这两个指针满足的交汇点是循环的起点，我们可以打破它。