LeetCode 142 Linked List Cycle Ⅱ 环形链表Ⅱ Java

题目：给一个链表的头节点head，返回链表进入循环的第一个节点，如果链表不是环形链表，返回null。

示例：

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为1的节点

示例2：

输入： head = [1,2], pos = 0
输出: 返回索引为0的节点

示例3：

输入： head = [1], pos = -1
输出:  返回null

解题思路：此处需要用到快慢指针指针进行解题。

第一步：确定是否是环形链表。我们假设快指针一次走两步，慢指针一次走一步。如果链表是环形链表，那么只要时间足够，快慢指针一定会相遇；反之快指针将会走到头（即遇见null），且不会与慢指针相遇。

第二步：确定链表为环形链表后，寻找它的循环起始节点。

1）设链表头到环入口的距离为x，环入口到快慢指针第一次相遇点的距离为y，相遇点再到环入口的距离为z；所以环的总大小为 y+z 如图：

2）当快慢指针第一次相遇的时候，慢指针走过的路程 S（慢）= x+y；快指针可能已经在环内走过了N圈，所以快指针的路程 S（快）= x+y+N*（y+z）；

3）路程 = 速度 * 时间，由于快指针的速度是慢指针的2倍，所以当时间一样时，快指针走过的路程时慢指针的2倍，即 2 * S（慢）= S（快），结合第二步我们得出 2 *（x+y）= x+y+N*（y+z);

4）化简得  x+y = N*（y+z) ；

5）移动y得： x= N*（y+z) -y；

6）从右侧取出1个y+z，得 x= (N-1)* (y+z) + (y+z)-y,

7）化简得到 x= (N-1)* (y+z) + z

8)上面式子可以看出，当N=1时，x=z；

9）由8可知，当我们将快慢指针中的一个指针（A）移动到head节点，另一个指针（B）继续指向快慢指针第一次相遇点，使两个指针同时以1的速度开始走，当B走完循环中剩下的路程z时，A刚好走完链表进入循环前的路程x，两指针相遇。

解题方法：

/**
 * 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) {
        ListNode fast = head;
        ListNode slow = head;

        //快指针当前非null，且下一步也非null，证明还未走完链表
        while (fast != null && fast.next != null) {
            //快指针速度为2
            fast = fast.next.next;
            //慢指针速度为1
            slow = slow.next;

            //快慢指针第1次相遇
            if (fast == slow) { 
                //将慢指针指向head
                slow = head; 
                while (fast != slow) { 
                    slow = slow.next;
                    fast = fast.next;
                }
                //两指针第二次相遇，即x=z时
                return fast;
            }
        }

        //当快指针走完了链表，证明链表为非环形链表
        return null;
    }
}