#include <stdio.h>
#include <malloc.h>
/*目的：检测指定的链表中是否存在循环*/
/*算法概要：同时指定p1,p2指向头节点，p1步长为1向后移，p2步长为2向后移*/
/*如果p1或p2指向NULL，说明不存在循环*/
/*如果存在循环，则p2经过循环必然会追上p1*/
/*算法的效率不是很高，但是却很简洁*/
/*author:dirtysalt,date:05.7.17,time:6:10*/
typedef struct list
{
struct list *next;
}list;
list *head=NULL,*tail=NULL;
void new_list()
{
tail=(list*)malloc(sizeof(list));
tail->next=NULL;
head=tail;
}
void add_item()
{
list *item;
item=(list*)malloc(sizeof(list));
item->next=head;
head=item;
}
void free_list()
{
list *tmp;
while(head!=tail)
{
tmp=head;
head=head->next;
free(tmp);
}
free(head);
}
void make_loop()
{
tail->next=head;
}
int check_list_loop()
/*return value 1:loop*/
/*0:!loop*/
{
list *p1=head,*p2=head;
while(((p1=p1->next)!=NULL)&&((p2=p2->next)!=NULL)&&((p2=p2->next)!=NULL))
{
if(p1==p2)
return 1;
}
return 0;
}
int main(int argc, char *argv[])
{
int i;
new_list();
for(i=0;i<10;i++)
add_item();
if(check_list_loop()==1)
printf("List Loop\n");
else
printf("List Non-Loop\n");
make_loop();
if(check_list_loop()==1)
printf("List Loop\n");
else
printf("List Non-Loop\n");
free_list();
return 0;
}