LeetCode142 链表的环 II

https://leetcode.com/problems/linked-list-cycle-ii/
解释转自https://blog.****.net/willduan1/article/details/50938210
如图所示，链表的整个长度为L，链表头head为h，假设fp和sp按照箭头所示的方向走。其中环入口点为d，h到d的距离hd为a。fp和sp假设初次相遇在c，初次相遇的时候慢指针sp肯定没有走完整个链表。设d到c的距离dc为x，h到c的距离即为sp初次相遇所走的路程，即设hc长度为s。此外设环的长度为r。而在fp和sp初次相遇在c点的时候，fp则在环内已经走了n圈。由于fp的速度是sp的2倍，接下来我们可以得出：
2s = s + nr
-> s = nr (1)
又因为hd距离为a，dc距离为x，hc距离为s，所以可以得出：
a + x = s (2)
结合(1)和(2)可以得出：
a + x = nr -> a + x = (n-1)r + r -> a + x = (n-1)r + (L-a) 注释：L-a即为环长r
-> a = (n-1)r + (L-a-x)
即此时h到d的距离a等于c到d的距离(L-a-x)。所以当fp和sp初次相遇在c点的时候，令fp从c点出发，sp指向
链表头h，两个同时以步数为1同时出发，则再次相遇的时候即为环的入口节点d。

public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow){
                ListNode slow2 = head; 
                while (slow2 != slow){
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow;
            }
        }
        return null;
    }