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

用户头像
Lee Chen
关注
发布于: 20 小时前

原题链接: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;

};

```



发布于: 20 小时前 阅读数: 4
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:142. 环形链表 II,JavaScript,快慢指针,详细注释