设快、慢两个指针:fast和slow,在程序开始时,二者都指向单链表的链表头,之后循环移动两指针,fast指针在一次循环中向前移动两步(fast=fast->next->next;),slow指针则只移动一步(slow=slow->next;),两指针进行追赶,若在任何一次循环中两指针指向同一结点,则说明此单链表中有回路;而若二者中任何一个指针指向了NULL(即到达了链表末尾),则说明此单链表中没有回路。
/* 判断链表是否有环 */
int hasLoop(Node *head)
{
Node *p1,*p2;
if(head == NULL || head->next == NULL) //链表为空,或是单结点链表直接返回头结点
return 0;
p1 = p2 = head;
while(p1->next != NULL && p1->next->next != NULL)
{
p1 = p1->next->next;
p2 = p2->next;
if(p1 == p2)
return 1;
}
return 0;