链表带环问题之判断链表是否带环

本文主要是介绍链表带环问题之判断链表是否带环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。

问题展示

在这里插入图片描述

一. 前言

在链表的学习中我们知道，常见的链表如下图所示：

那带环链表又是如何呢？

带环链表是指链表的最后一个节点的 NEXT 所指向的地址不再是“ 空指针 NULL ”，而是原链表中的一个随机节点，可能为头节点，也可能为中间节点，视情况而定。

具体如下：
在这里插入图片描述

二. 判断链表是否带环

在有了上面的了解后，我们将对如何判断链表是否带环进行讨论。
很多同学可能会想到说，我们可以直接找到链表的最后一个节点，判断它的 NEXT 指向是否为 NULL 不就可以很直白的得到是否带环了吗。可话是这么说，在上图中我们可以很轻松的看出链表的尾节点是哪一个，但这只是为了方便理解而画出的图，如果换成下面这样呢？

在这里插入图片描述
如果题目中没有明确的告知哪一个是头节点，又如何判断尾节点呢？

显然这种方法是不可行的。

但应对这种问题我们也不是毫无头绪，可以利用我们的“ 老朋友 ”：快慢指针来解决问题。在这里插入图片描述
我们让快慢指针同时指向链表的头部，之后让快指针每次在链表中走两个节点的位置，而慢指针每次走一个节点的位置，同时进行。

在经历一段时间后，快指针已经在环中走了很久，而慢指针刚刚进入环，如下图所示：
在这里插入图片描述
这时就不再是慢指针在后，快指针在前了，我们可以将其看作是快指针在慢指针的后面追赶，而我们再让它们前进一段时间后，快指针会和慢指针走到同样的位置，因为这时候他们的速度差为 1个节点（前面讲到过慢指针走一个节点，而快指针走两个节点），故不论慢指针进入环时他们相距多少距离，都一定会相遇，而当 fast == slow 时，我们就可以判断这个链表时带环得了。
在这里插入图片描述
再说链表不带环的情况：那就是快指针走到了链表的末尾，即快指针指向了 NULL 或快指针的NEXT指向了 NULL。

三. 代码展示

下面是代码展示：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode, * pListNode;
bool hasCycle(struct ListNode* head)
{pListNode slow = head;pListNode fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (fast == slow)return true;}return false;
}