leetcode经典例题第十题，在第九题的基础上判断环的入口位置。

题目描述

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

image

Follow up:

Can you solve it without using extra space?

解题思路

  • 同linked-list-cycle一题，使用快慢指针方法，判定是否存在环，并记录两指针相遇位置(Z)；
  • 将两指针分别放在链表头(X)和相遇位置(Z)，并改为相同速度推进，则两指针在环开始位置相遇(Y)

image

X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置。

由于快指针速度为慢指针速度的两倍，那么这个慢指针最多走圆的一圈（这里想象极端情况，就是整个链表就是一个环，那么两个指针从圆的同一个地方出发，那么此时何时相遇呢？必然是慢指针正好才走一圈的时候，快指针走两圈追上来了）。

所以这里假设就是在Z相遇的，那么慢指针走的距离是a+b，很好计算。而快指针走的距离是2(a+b)，此时我们想象，假设慢指针走到了X和Z的中间的时候，快指针已经到Z了，那么下面再走的话，就是快指针从Z点出发围着圆绕几圈之后恰好在Z点和X相遇，因此快指针走过的距离是：

2(a+b) = a+b+n*圆的周长 = a+b+n(b+c)

此时a为:

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

从公式上看，当一个指针从X出出发，走完a的距离之后，那么另一个指针从相遇点Z出发就会走(n-1)圈的环再加一个C的距离，此时正好在Y点相遇。

因此，一个指针从头出发，一个指针从相遇点出发，速度相同，相遇点就是环的入口节点。

代码提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        //一快一慢两指针先找到相遇点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        //万一没有环的话直接直接返回Null了
        if(fast == null || fast.next == null){
            return null;
        }
        //一个从head开始一步一步走，一个从相遇点开始一步一步走，再相遇就是环的入口位置
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}