6. 如何找到环的起点

方法二: 快慢指针

var hasCycle = function(head) { let dummyHead = new ListNode();

dummyHead.next = head;

let fast = slow = dummyHead;

// 零个结点或者一个结点，肯定无环 if(fast.next == null || fast.next.next == null)

return false;

while(fast && fast.next) { fast = fast.next.next;

slow = slow.next;

// 两者相遇了 if(fast == slow) {

return true;

} }

return false;

};

6. 如何找到环的起点

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

说明：不允许修改给定的链表。

思路分析

刚刚已经判断了如何判断出现环，那如何找到环的节点呢？我们来分析一波。

设快慢指针走了x秒，慢指针一秒走一次。

对快指针，有: 2x - L = m * S + Y -----①

对慢指针，有: x - L = n * S + Y -----②

其中，m、n 均为自然数。

• - ② * 2 得:

L = (m - n) * S - Y-----③

好，这是一个非常重要的等式。我们现在假设有一个新的指针在 L 段的最左端，慢指针现在还在相遇处。

让新指针和慢指针都每次走一步，那么，当新指针走了 L 步之后到达环起点，而与此同时，我们看看慢指针情况如何。

由③式，慢指针走了(m - n) * S - Y个单位，以环起点为参照物，相遇时的位置为 Y，而现在由Y + (m - n) * S - Y即(m - n) * S，得知慢指针实际上参照环起点，走了整整(m - n)圈。也就是说，慢

指针此时也到达了环起点。 :::tip 结论现在的解法就很清晰了，当快慢指针相遇之后，让新指针从头出发，和慢指针同时前进，且每次前进一步，两者相遇的地方，就是环起点。

编程实现

懂得原理之后，实现起来就容易很多了。

/**

• @param {ListNode} head
• @return {ListNode}

*/ var detectCycle = function(head) {

let dummyHead = new ListNode();

dummyHead.next = head;

let fast = slow = dummyHead;

// 零个结点或者一个结点，肯定无环 if(fast.next == null || fast.next.next == null)

return null;

while(fast && fast.next) {