c语言判断链表是否为循环链表

普通链表与循环链表的区别在于：普通链表的最后一个节点指向为NULL，而循环链表最后一个节点指向该链表中的任意一个节点，如同一个环。循环链表问题引出了一个在链表中很重要的概念：快、慢指针。快、慢指针可以帮助我们解决很多经典链表问题，详细如下。

普通链表与循环链表的示意图如下：

判断链表是否循环思路：定义两个指向头节点的指针，分别为fast和slow，从名字就可以看出一个指针为快指针，另一个为慢指针。定义快指针一次走两个节点的距离，而慢指针一次走一个节点的距离，入下图所示：

若fast指针走到NULL时说明链表不是一个循环链表，当fast与slow相等时，即他们指向同一个节点说明该链表是一个循环链表。因为在循环链表中，fast是slow的两倍速度，则fast迟早会从环中追到slow，这时候他们是指向同一个节点。

代码实现：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct ListNode //创建节点结构体
{
	int data;
	struct ListNode* next;
}LNode;

bool hasCycle(LNode* head)//bool值表示符合条件返回真，不符合条件返回假
{
	LNode* slow = head, * fast = head;//定义快慢指针

	while (fast && fast->next)//当fast或者fast的next为空时跳出循环
	{
		slow = slow->next;//slow走一步
		fast = fast->next->next;//fast走两步
		if (fast == slow)
			return true;//是循环链表返回真
	}
	return false;//当fast或者fast的next为空时说明不是循环链表，因此返回假
}

void Print(LNode* phead)//打印函数
{
	LNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");//模拟链表最后指向的是NULL
}

int main()
{
	LNode* n1 = (LNode*)malloc(sizeof(LNode));//创建5个节点，为了测试函数
	LNode* n2 = (LNode*)malloc(sizeof(LNode));
	LNode* n3 = (LNode*)malloc(sizeof(LNode));
	LNode* n4 = (LNode*)malloc(sizeof(LNode));
	LNode* n5 = (LNode*)malloc(sizeof(LNode));

	LNode* plist = n1;//指向头节点的头指针plist
	n1->data = 1;//给每个节点都赋值
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;

//设置循环链表
	n1->next = n2;//手动构建链表
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n3;//这里将n5指向n3，目的是设置循环链表
	
	if (hasCycle(plist) == false)
		printf("不是循环链表\n");
	else
		printf("是循环链表\n");

	return 0;
}

运行结果：