概念
快慢指针判断链表是否有环
Bool ifLoopOfList(List head){
List quick=NULL;
List slow=NULL;
quick=slow=head;
do{
quick=quick->next->next;
slow=slow->next;
printf("quick->%d\tslow->%d\n",quick->data,slow->data);
if(quick==slow){
return 1;
}
}while(quick);
return 0;
}
工程文件
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node,*List;
typedef int Bool;
List createLoopList(List head,int num,int loopSpot/*定义尾部的指向*/);
Bool ifLoopOfList(List head);
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
/**
判断链表是否有环这里用性能最优的快慢指针来实现
*/
int main(int argc, char *argv[]) {
List head=(List)malloc(sizeof(Node));
List ret=createLoopList(head,10,3/*定义尾部的指向*/);
if(ifLoopOfList(ret)){
printf("有环链表");
}else{
printf("无环链表");
}
printf("\n");
getchar();
return 0;
}
Bool ifLoopOfList(List head){
List quick=NULL;
List slow=NULL;
quick=slow=head;
do{
quick=quick->next->next;
slow=slow->next;
printf("quick->%d\tslow->%d\n",quick->data,slow->data);
if(quick==slow){
return 1;
}
}while(quick);
return 0;
}
List createLoopList(List head,int num,int loopSpot/*定义尾部的指向*/){
//尾插法
int i=1;
List p=head;
List q=head;
while(num--){
List new =(List)malloc(sizeof(Node));
new->data=i++;
p->next=new;
p=new;
}
/*
无环链表的创建
p->next=NULL;
p=head->next;
*/
for(i=0;i<loopSpot;i++){
q=q->next;
}
p->next=q;
q=head->next;
free(head);
return q;
}