题目描述
142#环形链表2
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。
进阶：
你是否可以不用额外空间解决此题？
分析
使用双指针可以解决该问题。
- 链表没有环的判定可以参考第141题，环形链表。
现在在链表有环的情况下分析。设一个快指针和一个慢指针，这两个指针的初始位置都在head，慢指针移动速度为1，快指针是它的两倍。
1536201429258
如图，设从head到环形开始结点的距离是A，慢指针从环形开始结点走到相遇点走过的路程是B，环的长度是L（画图的时候漏掉了，图中没有标示出来）。于是有：
- 对慢指针，从
head走到meet的距离为A+B - 对快指针，从
head走到meet的距离为2A+2B（因为快指针的速度是慢指针的两倍，而在相遇时它们走了相同的时间） - 相遇时，慢指针被快指针套了一圈，即快指针比慢指针多走一圈
根据以上分析我们可以列一个等式：A+B+L = 2A+2B，可以解得L = A + B。从这个结果可以看出，meet到begin的距离也是A。这意味着，如果我们分别放两个指针在head和meet，让它们以相同的速度前进，它们第一次相遇的地方就是我们要找的环形开始结点。
源码
/**
* 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 fast = head;
ListNode slow = head;
while (fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
if (fast == slow)
{
slow = head;
while (slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
