이중 링크 된 목록에서 반복하기

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

둘 다 우리가 말할 수있는 맞는 썼어 번에 두 단계 링크 된 목록이 그렇지 않으면 루프가 없습니다.

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

루프를 감지 한 후 우리는 하나 개의 루프를 사용할 수 있으며 처음부터 그것을 시작으로 느린 포인터를 이동 평소 속도, 포인터 모두 만남의 장소를 만날 때 루프의 시작이며, 우리가 할 수있는 부숴.