判断一个链表是不是循环链表
算法思想：在建立循环链表时设置两个指针，头指针和尾指针，head和tail,使tail->next=head,即让尾节点指向头节点，建立的时候采用尾插入法，每次让新节点先指向尾节点的下一个节点，
然后让头节点的下一个节点指向新节点，然后让新节点赋值给头节点和尾节点。
判断是否是循环链表时，也设置两个指针，慢指针和快指针，让快指针比慢指针每次移动快两次。如果快指针追赶上慢指针，则为循环链表，否则不是循环链表，如果快指针或者慢指针指向NULL，则不是循环链表。
include <iostream>
#include <cstdlib>
using namespace std;
typedef struct list
{
int data;
struct list *next;
}loopNode,*lpNode;
void createList(lpNode &list,int arr[],int n) //创建循环链表
{
lpNode node;
lpNode head=NULL,tail=NULL;
head=tail=list;
tail->next=head;
for(int i=0;i<n;i++)
{
node=(struct list*)malloc(sizeof(struct list));
node->data=arr[i];
node->next=tail->next;
head->next=node;
head=node;
tail=node;
}
cout<<"create success"<<endl;
}
int judgeIsLoop(lpNode list) //判断是否是循环链表
{
if(list==NULL)
return 0;
lpNode slow,fast;
slow=list;
fast=list->next->next;
while(slow)
{
if(fast==NULL||fast->next==NULL)
return 0;
else if(fast==slow||fast->next==slow)
return 1;
else
{
slow=slow->next;
fast=fast->next->next;
}
}
return 0;
}
void display(lpNode list) //输出循环链表
{
lpNode head,tail;
head=tail=list;
while(head->next!=tail)
{
cout<<head->data<<"--";
head=head->next;
}
cout<<head->data;
cout<<endl;
}
int main()
{
lpNode list=NULL;
int arr[10]={1,2,3,4,5,6,7,8,9,0};
int flag=0;
list=(struct list*)malloc(sizeof(struct list));
list->data=11;
list->next=NULL;
createList(list,arr,10);
flag= judgeIsLoop(list);
if(flag==1) //如果是循环链表，就输出循环链表
{
cout<<"the list is loop list."<<endl;
cout<<"output the list:"<<endl;
display(list);
}
else
{
cout<<"the list is not loop list."<<endl;
}
cout<<endl;
return 0;
}
运行截图：
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。