判断一个链表是不是循环链表

算法思想：在建立循环链表时设置两个指针，头指针和尾指针，head和tail,使tail->next=head,即让尾节点指向头节点，建立的时候采用尾插入法，每次让新节点先指向尾节点的下一个节点，

然后让头节点的下一个节点指向新节点，然后让新节点赋值给头节点和尾节点。

判断是否是循环链表时，也设置两个指针，慢指针和快指针，让快指针比慢指针每次移动快两次。如果快指针追赶上慢指针，则为循环链表，否则不是循环链表，如果快指针或者慢指针指向NULL，则不是循环链表。

include

#include

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

{

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"<

}

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<data<<"--";

head=head->next;

}

cout<data;

cout<

}

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."<

cout<<"output the list:"<

display(list);

}

else

{

cout<<"the list is not loop list."<

}

cout<

return 0;

}

运行截图：