链表是否有环的两种判断技巧
发布时间：2021-11-15 13:42:31 所属栏目：PHP教程 来源：互联网
导读：判断单链表是否有环 假设有一个含环链表：1-2-3-4-5-6-3（6又连接到3，形成一个环） 使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。当p从6走到3时，用了6步；此时q从head出发，则只需两步就到3，因而步数不等
|
判断单链表是否有环 假设有一个含环链表：1-2-3-4-5-6-3（6又连接到3，形成一个环） 使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。当p从6走到3时，用了6步；此时q从head出发，则只需两步就到3，因而步数不等，出现矛盾，存在环。而且可以锁定环的位置，就是q的步数+1 使用p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p == q，则存在环。虽然无法锁定环的位置，但是占用空间和时间少。这就是之前说的快慢链表里面的快慢指针。 实现: #include<iostream> #include<cstdio> using namespace std; const int MAXLEN = 6; struct Node{ int val; Node *next; }; int IfLoop(Node *head){ Node * cur1 = head; int pos1 = 0; while(cur1){ Node * cur2 = head; int pos2 = 0; pos1++; while(cur2){ pos2++; if(cur2==cur1){ if(pos1==pos2) break; else return pos2; } cur2 = cur2->next; } cur1 = cur1->next; } return -1; } bool IfLoop_2(Node *head){ Node * p = head; Node * q = head; while(p && q){ p = p->next; q = q->next; if(q) q = q->next; if (p && p==q) return true; } return false; } int main(){ Node *head = new Node; head->val = 0; Node *s = new Node; Node *p = new Node; head->next = p; for(int i=0;i<MAXLEN;++i){ p->val = i+1; p->next = s; p =s; s = new Node; } p->next = head->next->next; cout<<"位置在："<<IfLoop(head)<<"，如果位置是-1，则不存在"<<endl; return 0; }  （编辑：云计算网_泰州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330476号