环形链表 II 转载 https://blog.csdn.net/forever______/article/details/85103234#

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1输出：tail connects to node index 1解释：链表中有一个环，其尾部连接到第二个节点。复制代码

示例 2：

输入：head = [1,2], pos = 0输出：tail connects to node index 0解释：链表中有一个环，其尾部连接到第一个节点。复制代码

示例 3：

输入：head = [1], pos = -1输出：no cycle解释：链表中没有环。复制代码

用两个指针同时遍历链表，快指针每次走两步，慢指针每次走一步。如果链表中有环，那么他们终将相遇。可证：自他们相遇后，指针1从起点每次走一步，指针2从相遇点每次走一步，指针1和指针2相遇处就是环的起点。证明如下：

如下图，设Y点为环起点，Z点为快慢指针相遇点，abc为这几个关键节点间的路程（可能包括很多节点）。

因为，相遇时快指针走过的路程肯定为慢指针走过的路程的2倍。得：

(a+b)2 = a+b+(b+c)n //n>=1，n为快指针在相遇前绕环的圈数

解方程得 a = (b+c)(n-1)+c

所以：

当n=1时，a=c

当n>1时，a=c+n圈

得证。

时间复杂度O(n)

/** * 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 slow = head;        ListNode fast = head;        while( fast != null && fast.next != null ){            slow = slow.next ;             fast = fast.next.next;            if(slow == fast ){                break;            }        }        if( fast == null || fast.next== null ){            return null;        }        while( head != slow ){            head = head.next;            slow = slow.next;        }        return head;    }}复制代码