快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。判断单链表是否为循环链表：让快慢指针从链表头开始遍历，快指针向前移动两个位置，慢指针向前移动一个位置;如果快指针到达NULL，说明链表以NULL为结尾，不是循环链表。如果 快指针追上慢指针，则表示出现了循环。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
int num;
struct Node{
int x;
Node* next;
Node(int x):x(x),next(NULL) {}
};
Node* createNode(Node* &root,vector<int> &a){
int n=a.size();
if(n==0){
cout<<"数据错误"<<endl;
return root=NULL;
}else{
root = new Node(a[0]);
Node *p=root;
for(int i=1;i<n;i++){
Node *r=new Node(a[i]);
p->next=r;
p=r;
}
return root;
}
}
/*
可以利用快慢指针的思想来解答
当快慢指针相遇时说明有环
当快指针到达NULL是说明没有环
*/
bool hasCycle(Node *head)
{
Node *root=head;
if(root == NULL || root->next == NULL)
return 0;
else
{
Node *fast=root;
Node *slow=root;
while( fast != NULL && fast->next != NULL)
{
fast=fast->next->next;
slow=slow->next;
if(fast == slow)
return 1;
}
if(fast == NULL || fast->next == NULL)
return 0;
}
}
int main(){
vector<int> v;
cout<<"请输入节点个数"<<endl;
cin>>num;
for(int i=1;i<=num;i++){
int a;
cin>>a;
v.push_back(a);
}
Node *node;
Node *root=createNode(node,v);
if(hasCycle(root)){
cout<<"存在环"<<endl;
}else{
cout<<"不存在环"<<endl;
}
return 0;
}
转播
