141.环形链表
点击跳转leetcode原题
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
提示:
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
题解(快慢指针)
bool hasCycle(struct ListNode *head) {
struct ListNode*slow=head;//慢指针
struct ListNode*fast=head;//快指针
while(fast&&fast->next)
{
slow=slow->next;//慢指针走一步
fast=fast->next->next;//快指针走两步
if(slow==fast)
{
return true;
}
}
return false;
}
题解原理
定义一个慢指针和一个快指针在头节点,慢指针走一步,快指针走两步,如果链表存在环时,快指针会在慢指针进入环前不断地循环,直到慢指针进入环后与快指针相遇。同理,若快指针走到NULL且快慢指针并没有相遇则说明该链表不是环形链表。
怎么证明环形链表内快慢指针一定会相遇呢?
定义一个快指针和一个慢指针。
快指针走一步,慢指针走两步。
若链表内有环,快指针会比慢指针先进入环并在慢指针进环前不断在环里走下去。
但慢指针进入环,快指针开始追击,设慢指针进环时两指针距离为N,环长度为C,快慢指针速度差为一。
所以N步后两指针距离为0,两指针相遇。
那当慢指针走一步,快指针走三步时呢?
假设慢指针进环前走的长度为L,slow进环时,fast和slow的距离是N,环长度为C。X为快指针在慢指针进环前绕的圈数。
当慢指针进环时:
慢指针走过的距离为:L
快指针走过的距离为:L+X*C+C-N
快指针的速度是慢指针的三倍:3L=L+X*C+C-N
由上式推出得:2L=(X-1)C-N
等号左边一定是偶数(2与任意整数相乘结果都是偶数),故,当C与N都是偶数时等式成立。