c - 如何从链接列表中删除循环

Question

例如，如果链接列表是这样的：

1->2->3->4->5->6->7->8->9->4

我们可以使用弗洛伊德循环算法找到循环，但是在这种情况下如何去除循环呢？

Answer 1

1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop 
   node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

例如你的情况：1->2->3->4->5->6->7->8->9->4

1) Loop verified by Floyd's cycle detection algo.
2) count of nodes in loop = 6
3) head->1, p->7 (6th node from head)
4) Loop while head!=p head=head->next and p=p->next. Both will meet at node 4
5) p=p->next Loop while(p->next!=head) p=p->next;
   Put p->next=NULL after termination of above loop. Your new list will be 1->2->3->4->5->6->7->8->9->NULL

Answer 2

假设循环存在于链表中，在 C++ 中使用 Hashtable 或 map。

          map<struct node*, int> m;

            m[head]++;
            while (head->next != NULL) {
                if (m.find(head->next) != m.end()) {  
                    head->next = NULL;
                    break;
               } else m[head->next]++;
               head = head->next;
           }