LeetCode 142 Linked List Cycle Ⅱ 环形链表Ⅱ Java
题目：给一个链表的头节点head，返回链表进入循环的第一个节点，如果链表不是环形链表，返回null。示例：
示例1：
https://i-blog.csdnimg.cn/direct/50bcdd8298434f909db43f227d8b7da3.png
输入：head = , pos = 1
输出：返回索引为1的节点 示例2：
https://i-blog.csdnimg.cn/direct/c7922b10f1254c3d88ca0ada5376f8a2.png
输入： head = , pos = 0
输出: 返回索引为0的节点
示例3：
https://i-blog.csdnimg.cn/direct/17e59d7b61434a3097804245ee3aac28.png
输入： head = , pos = -1
输出:返回null 解题思绪：此处需要用到快慢指针指针举行解题。
第一步：确定是否是环形链表。我们假设快指针一次走两步，慢指针一次走一步。如果链表是环形链表，那么只要时间充足，快慢指针一定会相遇；反之快指针将会走到头（即遇见null），且不会与慢指针相遇。
第二步：确定链表为环形链表后，寻找它的循环起始节点。
1）设链表头到环入口的隔断为x，环入口到快慢指针第一次相遇点的隔断为y，相遇点再到环入口的隔断为z；所以环的总巨细为 y+z 如图：
https://i-blog.csdnimg.cn/direct/a0003cb70d9b468cbcace2971b25e755.png
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;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]