LeetCode142题 环形链表 II（Linked List Cycle II）
LeetCode142题 环形链表 II（Linked List Cycle II）
题目描述： 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。
分析
给出示意图：
示意图
对符号的一些说明：
符号说明 公式演算： 很容易得到： m=x+y（环的长度两种表示形式）; 快指针走两步，慢指针走一步。所以快指针的速度是慢指针的速度的二倍，所以相同时间内，快指针走的长度也是慢指针走的长度的二倍： 有：f=2s; 在快指针走过 圈后两指针相遇，有: m+kn+y=2(m+y); 去括号后有：m+kn=2m+y; 解得：m=kn-y; 又因为:n=x+y; 所以有：m=kn-(n-x); 所以：m=x+n(k-1)。 m是头节点到环起点的长度； x是相遇点到头节点的长度； x-m是(k-1)个环的长度。 通过公式的演算，我们能够明白： 找到相遇点后，链表头节点与相遇点节点同时出发，相遇处便是环的起点。相遇点节点多走了(k-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)
return null;
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;
fast = head;
while(slow != fast){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
对代码的解释： 1、如果head是空，则不存在环，直接返回null； 2、设置快慢指针开始均指向head，设置循环条件，快指针不为空且快指针的next域指向的不为空进入循环，其中空指针的next域的指向不为空保证快指针可以走两步，否则有可能出现空指针异常； 3、如果快慢指针指向相同节点，则break掉，是相遇点； 4、第一次循环过后，如果fast为空或者fast.next为空，则不存在环，返回null； 5、如果存在环，让fast指针从开始移动，slow指针从相遇点移动，相遇则为起点，将其return即可。
欢迎关注
长按下方二维码即可关注微信公众号:code随笔
微信公众号:code随笔