一、题目要求
- 给你一个链表的头节点
head，判断链表中是否有环。- 如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。- 如果链表中存在环 ，则返回
true。 否则，返回false。
题目：OJ-环形链表
二、解题思路
我们可以使用快慢指针来解决此问题：
- 定义一个快指针fast，一个慢指针low。这两个指针都指向头节点head。
- 开始遍历链表节点。快指针每次走两步，慢指针每次走一步。
- 如果链表没有环，则快指针最终会指向链表尾部，返回false。
- 如果链表有环，由于快指针每次比慢指针多走一步，快慢指针之间的距离在不断缩短，则快慢指针一定会相遇，此时返回true。
三、代码实现
bool hasCycle(struct ListNode *head) { struct ListNode *low = head; struct ListNode *fast = head; while(fast && fast->next) { low = low->next; fast = fast->next->next; if(low == fast) return true; } return false; }
四、关于快慢指针步数差值的探讨
上述解题思路中，快慢指针的步数差值为1，则快慢指针一定会相遇。那么如果它们的差值不为1呢？会不会有永远遇不到的可能性存在呢？
这里假设慢指针一次走一步，快指针一次走三步，它们的差值为2。
下图的时刻为，slow指针刚刚进入环，fast指针已经走了x圈。
- 如果N是偶数，那么fast和slow一定会相遇
- 如果N是奇数，那么fast会刚好越过slow一个位置，它们之间的距离会变成C - 1
- 这时需要讨论C - 1的奇偶性：
- 如果C - 1为偶数，fast和slow一定会相遇，此时C为奇数
- 如果C - 1为奇数，fast会刚好越过slow一个位置，它们之间的距离会变成C - 1，由于C - 1为奇数，会重新进入该情况，此时它们永远不会相遇，此时C为偶数
总结以上情况：当N为奇数、C为偶数时，fast和slow永远不会相遇
现在确定了不会相遇时N和C的关系，只需要找出一个关于N和C的关系式来验证这个关系是否正确，就可以确定在该情况下是否有永远追不上的可能性。
- slow走过的路程：L
- fast走过的路程：L + x * C + （C - N） = 3 * L
化简如下：（把上述假设的关系带入），会发现此等式不成立，故假设不成立
- 2L = （x + 1）C - N （x为fast走过的完整的圈数）
- 偶 偶 奇
所以在当slow指针一次走一步，fast指针一次走三步，它们的差值为2的情况下，它们一定会相遇。不存在永不相遇的可能性。
其他的步数差值也可用这种思路来求解，但讨论的情况会相对复杂。
