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

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

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

复制代码

示例2：

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

复制代码

示例3：

1. 输入： head = [1], pos = -1
2. 输出:  返回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，两指针相遇。
解题方法：
  

1. /**
2. * Definition for singly-linked list.
3. * class ListNode {
4. * int val;
5. * ListNode next;
6. * ListNode(int x) {
7. * val = x;
8. * next = null;
9. * }
10. * }
11. */
12. public class Solution {
13.     public ListNode detectCycle(ListNode head) {
14.         ListNode fast = head;
15.         ListNode slow = head;
17.         //快指针当前非null，且下一步也非null，证明还未走完链表
18.         while (fast != null && fast.next != null) {
19.             //快指针速度为2
20.             fast = fast.next.next;
21.             //慢指针速度为1
22.             slow = slow.next;
24.             //快慢指针第1次相遇
25.             if (fast == slow) {
26.                 //将慢指针指向head
27.                 slow = head;
28.                 while (fast != slow) {
29.                     slow = slow.next;
30.                     fast = fast.next;
31.                 }
32.                 //两指针第二次相遇，即x=z时
33.                 return fast;
34.             }
35.         }
37.         //当快指针走完了链表，证明链表为非环形链表
38.         return null;
39.     }
40. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。