给定一个链表，判断链表是否存在环路。下图显示了一个带有循环的链表。这里有不同的实现方式方案一：哈希法：循环遍历链表，始终将节点地址放入哈希表中。在任何时候，如果达到NULL，则返回false，如果当前节点的next指向先前存储在Hash中的任何节点，则返回true。#includeusingnamespacestd;structNode{intdata;structNode*next;};voidpush(structNode**head_ref,intnew_data){structNode*new_node=newNode;new_node->data=new_data;new_node->next=(*head_ref);(*head_ref)=new_node;}booldetectLoop(structNode*h){unordered_sets;while(h!=NULL){if(s.find(h)!=s.end())returntrue;s.insert(h);h=h->next;}returnfalse;}intmain(){structNode*head=NULL;push(&head,20);push(&head,4);push(&head,15);push(&head,10);head->next->next->next->next=head;if(detectLoop(head))cout<<"Loopfound";elsecout<<"NoLoop";return0;}复杂度分析：时间复杂度：O(n)。只循环一次。辅助空间：O(n)。n是在hashmap中存储值所需的空间。方案二：这个问题不用hashmap也可以通过修改链表数据结构来解决。处理方法：该方案需要修改基本的链表数据结构。每个节点都有一个访问标志。遍历链表，继续标记访问过的节点。如果再次看到访问过的节点，则存在循环。此解决方案在O(n)中有效，但需要每个节点的附加信息。该解决方案的一种变体不需要修改基础数据结构，可以使用散列来实现，只需将访问节点的地址存储在散列中，如果您看到散列中已经存在一个地址，则它存在一个循环。C++：#includeusingnamespacestd;structNode{intdata;structNode*next;intflag;};voidpush(structNode**head_ref,intnew_data){structNode*new_node=newNode;new_node->data=new_data;new_node->flag=0;new_node->next=(*head_ref);(*head_ref)=new_node;}booldetectLoop(structNode*h){while(h!=NULL){if(h->flag==1)返回真;h->flag=1;h=h->next;}returnfalse;}intmain(){structNode*head=NULL;push(&head,20);push(&head,4);push(&head,15);push(&head,10);head->next->next->next->next=head;if(detectLoop(head))cout<<"Loopfound";elsecout<<"NoLoop";return0;}复杂度分析：时间复杂度：O(n)。只循环一次。辅助空间：O(1)。不需要额外的空间。方案三：弗洛伊德循环搜索算法方法：这是最快的方法，如下所述：使用两个指针遍历链表。将一个指针(slow_p)移动一个，将另一个指针(fast_p)移动两个。如果这些指针在同一个节点相遇，则存在一个循环。如果指针不适合，链表就没有循环。Floyd循环搜索算法的实现：#includeusingnamespacestd;classNode{public:intdata;Node*next;};voidpush(Node**head_ref,intnew_data){Node*new_node=newNode();new_node->data=new_data;new_node->next=(*head_ref);(*head_ref)=new_node;}intdetectLoop(Node*list){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){return1;}}return0;}intmain(){Node*head=NULL;push(&head,20);push(&head,4);push(&head,15);push(&head,10);head->next->next->next->next=head;if(detectLoop(head))cout<<"Loopfound";elscout<<"无循环";return0;}方案四：在不修改链表数据结构的情况下标记访问过的节点该方法中会创建一个临时节点。使遍历的每个节点的next指针指向这个临时节点。这样我们就用结点的next指针作为标志，表示该结点是否已经遍历。检查每个节点以查看下一个节点是否指向临时节点。在循环的第一个节点的情况下，第二次通过条件会为真，所以我们发现循环存在。如果遇到指向null的节点，则循环不存在。下面是上述方法的实现：#includeusingnamespacestd;structNode{intkey;structNode*next;};Node*newNode(intkey){Node*temp=newNode;temp->key=key;temp->next=NULL;returntemp;}voidprintList(Node*head){while(head!=NULL){cout<key<<"";head=head->next;}cout<next==NULL){returnfalse;}if(head->next==temp){returntrue;}Node*nex=head->next;head->next=temp;head=nex;}returnfalse;}intmain(){Node*head=newNode(1);head->next=newNode(2);head->next->next=newNode(3);head->next->next->next=newNode(4);head->next->next->next->next=newNode(5);head->next->next->next->next->next=head->next->next;boolfound=detectLoop(head);if(found)cout<<"LoopF??ound";elsecout<<"NoLoop";return0;}复杂度分析：时间复杂度：O(n)。只循环一次。辅助空间：O(1)。不需要空间。解决方案5：存储长度在该方法中，创建了两个指针，第一个（始终指向头部）和最后一个指针。每次最后一个指针移动时，我们计算第一个和最后一个之间的节点数，并检查当前节点数是否大于前一个，如果是，我们通过移动最后一个指针来完成，否则这意味着我们'已经到达循环的末尾，因此我们相应地返回输出。#includeusingnamespacestd;structNode{intkey;structNode*next;};Node*newNode(intkey){Node*temp=newNode;temp->key=key;temp->next=NULL;returntemp;}voidprintList(Node*head){while(head!=NULL){cout<key<<"";head=head->next;}cout<next;}returncounter+1;}booldetectLoop(Node*head)Node*temp=newNode;Node*first,*last;first=head;last=head;intcurrent_length=0;intprev_length=-1;while(current_length>prev_length&&last!=NULL){prev_length=current_length;current_length=distance(first,last);last=last->next;}if(last==NULL){returnfalse;}else{returntrue;}}intmain(){Node*head=newNode(1);head->next=newNode(2);head->next->next=newNode(3);head->next->next->next=newNode(4);head->next->next->next->next=newNode(5);head->next->下一步->下一步->下一步->next=head->next->next;boolfound=detectLoop(head);if(found)cout<<"LoopF??ound";elsecout<<"NoLoopF??ound";return0;}}
