问题链接
问题描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
- 不允许修改 链表。
示例
解题思路
核心：数学分析、双指针
- 用快慢指针证明环（这里的具体做法不再赘述,具体可见LeetCode：141. 环形链表）
- 假设链表共有
a+b个节点，其中 链表头部到链表入口 有a个节点（不计链表入口节点）， 链表环 有b个节点，快指针速度为f,慢指针速度为s，第一次相遇耗时t，可得：ft=st + nb（快指针多跑了n圈环） - 按照我们快慢指针的做法，快指针速度是慢指针的2倍：
ft = 2st
亦可推出：st = nb，也就是说第一次相遇，慢指针了跑了nb的距离
如果此时，慢指针再跑a步，距离为：a+nb，根据这个距离式子，可知此时慢指针又回到环的入口！ - 因此，我们将已经没有用的快指针重新放在链表头节点，快慢指针以相同的速度
1跑，当跑出距离a，快慢节点都走到了环的起点，再次相遇。
代码示例（JAVA）
/**
* 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, slow = head;
while (true) {
if (fast == null || fast.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
时间复杂度：O(n)
