环形链表

• • • • 1.题目
      • 2.画图理解
      • 3.代码的实现

1.题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

链表带环：

链表不带环：

2.画图理解

链表带环的情况：

如果链表不带环，fast会走向空

3.代码的实现

bool hasCycle(struct ListNode *head) {//使用快慢指针：slow一次走一步，fast一次走两步，如果fast等于slow则说明链表带环//如果fast或者fast->next为空，代表链表没有环struct ListNode* slow = head, *fast = head;while(fast && fast->next){//slow一次走一步，fast一次走两步slow=slow->next;fast=fast->next->next;//如果fast等于slow则说明链表带环if(slow==fast){return ture;}}retrun false;
}

扩展问题：

1.为什么slow一次走1步和fast一次走2步一定会在环中相遇？
2.如果slow一次走1步，fast一次走n（n>2）步还会相遇吗？

问题1：为什么slow一次走1步和fast一次走2步一定会在环中相遇？
分析证明：
1.slow和fast，一定是fast先进环，这时slow走了如环前距离的一半

2.随着slow进环，fast已经在环里面走一段距离了，走的距离的长短和环的大小有关，假设slow进环的时候，slow和fast的距离是N，fast开始追slow，slow每次往前走一步，fast走2步，没走一次，fast离slow的距离就进一步，他们之间距离走到0的时候就是相遇点；fast和slow的距离变化：N，N-1，N-2，N-3…1，0；

因此，slow一次走1步和fast一次走2步一定会相遇。

问题2：如果slow一次走1步，fast一次走n（n>2）步还会相遇吗？

分析证明：（和slow一次走1步和fast一次走2步推理过程一样）
1.假设slow一次走1步，fast一次走3步
slow进环以后，fast跟slow之间的距离为N，fast开始追slow

slow和fast之间的距离变化：

如果N是奇数，fast和sow之间的距离变成-1，说明fast和slow之间的距离是C-1（C是环的长度），如果C-1是奇数，那么永远追不上，如果C-1是偶数，则可以追上。

假设slow一次走1步，fast一次走4步
slow进环以后，fast跟slow之间的距离为N，fast开始追slow

-1意味着slow和fast的距离是C-1；-2意味着距离是C-2，如果C-1和C-2是3的倍数，则可以追上，否则就追不上。

以上分析可以得出slow一次走一步，fast一次走n步，不一定会相遇。

完结！