LeetCode 题解：142. 环形链表 II，JavaScript，快慢指针，详细注释

原题链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/



解题思路：



1. 用快慢指针先查找链表是否有环。

2. 如果有环，则从链表起点和快慢指针相遇点向前走，必然会在环的连接点相遇。

3. 解法的证明可以参考官方题解的第二点。



```javascript []

/**

* Definition for singly-linked list.

* function ListNode(val) {

* this.val = val;

* this.next = null;

* }

*/



/**

* @param {ListNode} head

* @return {ListNode}

*/

var detectCycle = function (head) {

// 如果链表为空，或者链表只有一个元素且无环，此时指针无法行动，则返回null

if (!head || !head.next) {

return null;

}



// 创建快慢指针

let slow = head;

let fast = head;



// 如果快指针无法移动，则退出循环

while (fast && fast.next) {

// 慢指针走一步，快指针走两步

slow = slow.next;

fast = fast.next.next;



// 如果两个指针的指向相同，则表示已经查找到环。

// 但两个指针相遇的节点不一定是环的连接点，而是在环的某个位置

if (slow === fast) {

break;

}

}



// 前面的退出循环条件有两个，一个是没有找到环，一个是找到了环

// 通过快慢指针是否相同，判断是否找到环，如果没有，则返回null

if (slow !== fast) {

return null;

}



// 如果有环，而且快指针的速度是慢指针的两倍。

// 因此如果创建两个指针，从链表起始点和快慢指针相遇节点分别出发。

// 两者相遇的节点必然是环的连接点。

let startNode = head;

let meetNode = fast;



// 遍历链表，查找连接点，如果两个指针相等，则表示找到连接点。

while (startNode !== meetNode) {

startNode = startNode.next;

meetNode = meetNode.next;

}



return meetNode;

};

```