赞
踩
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
slow和fast指向链表的开始,slow一次走一步,fast一次走两步。
不带环,fast就会为空。
带环,fast就会在环里面追上slow。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode* slow=head,*fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { return true; } } return false; }
1、slow一次走一步,fast一次走两步,为什么slow和fast一定会在环中相遇?会不会在环里面错过,永远遇不上?请证明一下。
分析证明:
第一步: slow和fast,fast一定是先进环,这时slow走了入环前距离的一半。
第二步:随着slow进环,fast已经在环里面走了一段,走了多少跟环的大小有关系。假设slow进环的时候,fast到slow的距离是N,fast开始追slow。slow每次往前走1步,fast往前走2步,每追1次,判断一下是否相遇。
每追1次,fast和slow的距离变化:N,N-1,N-2,N-3,… ,1,0。
每追1次,距离减少1,他们之间的距离最后减到0的时候就是相遇的点。
结论:他们一定会相遇。
2、为什么slow走一步,fast走的两 步呢?能不能fast走一次走n步(n >2)?请证明一下
假设:slow一次走1步,fast一次走3步。
slow进环以后,fast跟slow之间的距离为N,fast开始追slow。
每追1次,fast和slow的距离变化:
N是偶数:N,N-2,N-4,N-6,… 4,2,0,可以追上。
N是奇数:N,N-2,N-4,N-6,… ,3,1,-1,这一次追不上。
如果N是奇数,距离变成-1意味着他们之间的距离变成C-1(C是环的长度)。如果C-1是奇数,那么就永远追不上了。如果C-1是偶数,那么就可以追上。
假设:slow一次走1步,fast一次走4步。
slow进环以后,fast跟slow之间的距离为N,fast开始追slow。
每追1次,fast和slow的距离变化:
N是3的倍数:N,N-3,N-6,N-9,… 6,3,0,可以追上。
N不是3的倍数:
1:N,N-3,N-6,N-9,… ,2,-1,这一次追不上。
2:N,N-3,N-6,N-9,… ,1,-2,这一次追不上。
假设C是环的长度-1意味着距离是C-1,-2意味着距离是C-2。如果C-1和C-2是3的倍数就可以追上否则就追不上。
结论: fast一次走n步? n >2不一定会相遇。
slow走1步,fast走2步,一定会相遇。如何求环的入口点呢?
假设:从头节点到环的入口的距离为L,环的长度为C,慢指针入环走的距离为X。
则:
满指针走的距离:L+X
快指针走的距离:L+NC+X (N>=1)
N是他们相遇之前,fast在环里面走的圈数。
而快指针走的路程是慢指针的2倍。
则:
2(L+X) = L+NC+X
L+X = NC
L = NC-X
L = (N-1)*C +C-X
(N-1)*C:从相遇点有走回到相遇点。
结论:一个指针从相遇点开始走,一个指针从链表头开始走,他们会在环的入口点相遇。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow=head,*fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { //相遇,链表带环 struct ListNode* meet=slow; struct ListNode* slow=head; while(slow!=meet) { //公式证明的,具体请看上文 slow=slow->next; meet=meet->next; } return meet; } } return NULL; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。