LeetCode(142)- Linked List Cycle II(找到有环链表环入口)

题目：

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node. Example 2:

Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node. Example 3:

Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.

翻译：

给定一个链表，返回循环开始的节点。如果没有循环，返回null。 为了在给定的链表中表示一个循环，我们使用一个整数pos，它表示tail连接到的链表中的位置(0索引)。如果pos为-1，则链表中没有循环。 注意:不要修改链表。

思路：

如果单链表有环，当slow指针和fast指针相遇时，slow指针还没有遍历完链表，而fast指针已经在环内循环n（n>=1）圈了，假设此时slow指针走了s步，fast指针走了2s步，r为fast在环内转了一圈的步数，a为从链表头到入口点的步数，b为从入口点到相遇点的步数，c为从相遇点再走c步到达入口点，L为整个链表的长度。

slow指针走的步数： s = a + b fast指针走的步数： 2s = s + nr 即：s = nr 链表的长度： L = a + b + c = a+r 由上可得： a + b = n*r = (n - 1)*r + r 而r = L - a，所以： a + b = (n - 1)*r + L - a a = (n - 1)*r + L - a - b 而L - a - b = c，所以： a = (n -1)*r +c **综上可得：**从链表头到环入口点等于(n - 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) { if(head==null || head.next==null) return null; ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(slow==fast){ break; } } if(fast==null ||fast.next==null) return null; slow=head; while(slow!=fast){ fast=fast.next; slow=slow.next; } return slow; } }