面试题 02.08. 环路检测-快慢指针+如何找到环的入口？（证明）Java_快慢指针找环

1.题目

 

2.思路

方法一——哈希表记录节点

思路很简单，记录一下每个节点出现的次数，如果某个节点出现了两次，代表此时有环，并且是环的入口，直接返回即可。

时间复杂度O(N)

空间复杂度O(N)

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

方法二——快慢指针找到环 + temp指针找到环的入口

想法：首先把问题拆分成两个问题，第一个问题判断是否有环。第二个问题，如果有环的话，如何判断环的入口呢？并且保证空间复杂度为O（1）。

第一个问题很好解决。直接快慢指针就可以。

slow指针走一步

fast指针走两步

如果链表存在环，那么必然fast指针和slow指针会相遇。为什么呢？

简单的正面如下：

假如slow刚好走到环的入口，此时fast指针必然在环中的任意一个位置，此时他们之间的距离为length, 这个长度length 必然小于环的大小。

每一次，fast 都会比slow多走一步，所以下次他们之间的距离为length-1.

再下一次他们的距离为length - 2.

...

直到他们两相遇！！！

并且可以得到的是，slow不会走过一圈，他们就会相遇！因为这个距离length小于环的大小。

如果链表存在环，那么如何找到环的入口呢？（变形：如何求出环的大小？）

先说结论。此时定义一个temp指针，指向 head, 让slow 和 temp同时移动，他们相等的时候就是环的入口。

证明如下：（借用官方题解的一个图）

a : 起点到环的入口的举例为a

b：环的入口到快慢指针相遇的位置。

c：环的大小减去b的距离

首先可以得知slow指针移动的距离： a + b

然后可以得知fast指针移动的距离：a + b + n * (b + c)

然后利用fast指针速度是slow指针的两倍，所以在相同的时间下，距离也应该是两倍关系。

所以有2 *(a + b) = a + b + n * (b + c)

因为我们要计算a，所以我们想办法把a放在左边，那么化简可以得到

a = nb - b + nc

这样看不出来什么东西，所以进一步想，因为有环的大小为b + c，所以想办法凑在一起。有

a = (n - 1) * (b + c) + c

这时候可以发现，

左边的值等于一个temp指针从起点走到环的入口

右边的值相当于是slow指针先走距离c, 到达环的入口，然后再走n - 1 圈，直到两个相遇！！！！！！！

所以有结论：当快慢指针相等的时候，让slow 和 temp同时移动，他们相等的时候就是环的入口。

时间复杂度O(N)

空间复杂度O(1)

/**
 * 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) {
        // 时间O(n)
        // 空间O(1),这里使用的是三个指针，不占用空间
        ListNode slow = new ListNode(-1), fast = new ListNode(-1);
        slow = head;
        fast = head;
        while(fast != null){
            if(fast.next != null && fast.next.next != null){
                fast = fast.next.next;
            }
            else
                return null;
            slow = slow.next;
            if(slow == fast){ //代表有循环
                // 找到环的入口
                ListNode temp = head;
                while(temp != slow){
                    temp = temp.next;
                    slow = slow.next;
                }
                return temp;
            }
        }
       
        return null;
        
       
    }
}

3.结果

4.类似的题

判断是否有环？

判断环的大小？

删除倒数第K个数？