题目描述
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出null。
数据范围
节点 val 值取值范围 [1,1000]。
节点 val 值各不相同。
链表长度 [0,500]。
样例
给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
思路阐述及口诀
#主要考察两知识点:
(1)判断链表是否环;
(2)如果有环,如何找到这个环的入口
#判断链表是否有环:
可以使用快慢指针法, 分别定义 fast 和 slow指针,
从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,
如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。
#找到这个环的入口:
从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点,
那么当这两个指针相遇的时候就是 环形入口的节点。 (证明略)
参考题解
(链表,快慢指针扫描) O(n)
本题的做法比较巧妙。
用两个指针 first,second 分别从起点开始走,first 每次走一步,second 每次走两步。
如果过程中 second走到null,则说明不存在环。
否则当first 和 second 相遇后,让first 返回起点,second待在原地不动,然后两个指针每次分别走一步,
当相遇时,相遇点就是环的入口。
算法1
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
if(head==null||head.next==null)
return null;
ListNode fast=head,slow=head;
while(fast!=null&&slow!=null)
{
slow=slow.next;
fast=fast.next;
if(fast!=null)
fast=fast.next;
else
return null;
if(fast==slow) //有环
{
// 两个指针,从头结点和相遇结点,各走一步,直到相遇,相遇点即为环入口
fast=head;
while(fast!=slow)
{
fast=fast.next;
slow=slow.next;
}
return fast; //当这两个指针相遇的时候就是 环形入口的节点
}
}
return null;
}
}
算法2
# 我看不懂,但我大受震撼