题目描述
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
相关话题: 链表、双指针 难度: 中等
示例 1:
示例 2:
示例 3:
进阶:
你是否可以不用额外空间解决此题?
思路:这道题需要先确定链表有环,方法同leetcode 141. 环形链表。
- 定义两个指针,慢指针
slow
和快指针fast
,慢指针一次走一步,快指针一次走两步; - 当慢指针和快指针重合,即
slow == fast
,确定链表有环,此时慢指针slow
回到链表头部,快指针fast
和慢指针slow
每次走一步,当慢指针和快指针再次重合,重合的节点就是环的入口节点。
证明:
如图,无环部分长度为
L
,有环部分长度为R
,第一次相遇指针离入环节点距离为C
。假设
t
时刻,slow
和fast
指针相遇,则两式相减,,可以看出slow
指针和fast
指针的距离为环长度的倍数,那么它们必定会在某个时刻相遇。
证明它们会相遇之后,我们反证法证明第二次相遇的位置就是环的入口节点。
已知它们t
时刻会在入口节点相遇,
整理得,。可以理解为fast
指针比slow
指针领先了C
步,看成fast
指针退后C
步出发,slow
指针从链表头出发,刚好相差kR
,也就是说slow
走过L
来到入口节点时,fast
也在入口节点,不矛盾。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null)
return null;
ListNode slow = head;
ListNode fast = head;
//slow一次走一步,fast一次走两步,如果相遇就是有环
while(fast.next != null&&fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
//有环
if(slow == fast){
slow = head;//slow指针回到head
//slow和fast变成每次走一步,相遇时就是入口节点
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}