34. 链表中环的入口结点
题目描述
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出null
。
数据范围
节点 val 值取值范围 [1,1000]。
链表长度 [0,500]。
样例
给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。
所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
算法 快慢指针
经典的快慢指针问题
算法流程
快慢指针同时走,快指针每次走两步,慢指针每次走1步
如果快指针走到空,则说明不存在环
否则当快慢指针相遇后,让慢指针回到起点,快指针不动
然后快慢指针分别走一步,相遇点就是环入口
算法证明
图中a为起点,b为环入口,c是快慢指针第一次相遇点,ab之间距离为x,bc之间距离为y
1)证明第二次相遇点就是环的入口
证明1:m表示从环的长度
第一次相遇时,慢指针走了x+y步
快指针距离=x+m*k+y(k为圈数)
又因为快指针走过距离是慢指针的两倍2(x+y)
所以 x +km+y = 2(x + y)
可以得到 x = km-y
如果让快指针从c点开始走,走x步,刚好到b点
慢指针(相当于走k圈过后又回退y步,刚好到b)
则让慢指针从起点a开始,走x步,也会到b点
所以第二次相遇点就是环入口b点
证明2:z表示从c顺时针到b的距离
第一次相遇时,慢指针走x+y
快指针走x+(y+z)*k+y = 2(x+y)
得到 x=(k-1)(y+z) + z
如果让快指针从c开始走,则经x步刚好到b
此时让慢指针从a开始,走x,也刚好到b
所以第二次相遇点是b
2)证明快慢指针必定相遇
数学归纳法:快慢指针距离k
相距1格,下次相遇。(1步相遇)
相距2格,下一次移动,变为相距1格。(2步相遇)
相距k格,每次环内移动,距离缩短1,直至相距2格。
根据数学归纳法,快慢指针一定能相遇
时间复杂度
$O(n^2)$
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if(!head || !head->next) return nullptr; //空节点则无环
ListNode *fast = head, *slow = head;
while(fast && slow)
{
slow = slow->next; //快指针走1步
fast = fast->next;
if(fast) fast = fast->next; //慢指针走2步
else return nullptr; //出现空节点则没有环
if(fast == slow) //第一次相遇
{
slow = head; //慢指针回到原点
while(fast != slow) //快慢指针都走1步
{
fast = fast->next;
slow = slow->next;
}
return slow; //第二次相遇
}
}
return nullptr;
}
};
总结
经典例题,需要好好理解