判断链表中是否有环（C语言）_c语言如何判断一个单链表是否有环

作者：盐析白兔 | 2024-02-06 20:57:57

踩

c语言如何判断一个单链表是否有环

声明：题目来源：力扣（LeetCode）

给定一个链表，判断链表中是否有环。

题目链接：环形链表

示例1：
在这里插入图片描述
输出：true

示例2：
在这里插入图片描述
输出：true

示例3：
在这里插入图片描述
输出：false

解题思路：首先从环的性质入手，如果存在环，那么我若是使用一个指针遍历链表，这个指针将会一直在链表中的环里转圈圈。那要如何判断是否有环也就显而易见了：若是指针访问到了之前访问过的节点，那么链表有环，若是能遍历完链表，那肯定没有。
那么问题来了，怎么判断指针是否访问过了之前的节点？以下介绍三种方法：

方法1：暴力破解法，记录每个遍历过的节点地址，每访问一个节点就比较一次，若有相等的地址，则返回该地址值；

方法2：设置两个速度不同的指针同时从链表的第一个节点开始遍历链表，一个快指针 fp 每次移动两个节点，一个慢指针sp每次移动一个节点，若两个指针能相遇，则存在环。（注：这里的慢指针中保存的即为快指针访问过的节点）

方法3：将每个访问过的节点的 next 指针指向前一个节点，这样当指针访问到最后一个节点时，

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/64544