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

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

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

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

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

代码实现：

#include

#include

#include

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;

}

运行结果：

代码中我们将n5->next = n3;因此该链表为循环链表，运行结果符合逻辑。

结语：

以上就是判断链表是否循环的解法，用到的快、慢指针概念是链表中非常经典的一种解题手法，希望本文可以对你起到帮助。（￣︶￣）↗