C语言 如何从链表中删除循环

Question

例如，如果链接列表如下:

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

我们可以使用Floyd循环算法找到循环，但是在这种情况下如何去除循环呢?

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++中的哈希表或映射。

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