LeetCode 142.环形链表II - JavaScript
LeetCode 142.环形链表II - JavaScript
心谭博客
发布于 2020-04-21 10:41:31
发布于 2020-04-21 10:41:31
题目描述：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
这题在《LeetCode 141.环形链表》的基础上，需要寻找环的入口处。
解法 1：Floyd 算法
依然使用 Floyd 算法，来判断链表是否有环。若存在环，那么算法返回的节点就是快慢指针相遇的节点。
令 ptr1 是开始节点，ptr2 是相遇节点，它们每次都向后移动一个位置，两个节点相遇的位置就是环的入口处。
代码实现如下：
// ac地址：https://leetcode-cn.com/problems/linked-list-cycle-ii/
// 原文地址：https://xxoo521.com/2020-03-03-linked-list-cycle-ii/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
let intersect = getIntersect(head);
if (!intersect) {
return null;
}
let ptr1 = head;
let ptr2 = intersect;
while (ptr1 !== ptr2) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return ptr2;
};
/**
* 找到相遇点
* @param {ListNode} head
* @return {ListNode}
*/
function getIntersect(head) {
let fast = head;
let slow = head;
while (slow && fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return slow;
}
}
return null;
}解法 2: 哈希表
使用哈希表来记录节点是否出现过。若存在环，那么一直向下访问节点，一定会回到重复节点。且这个节点就是环的入口处。如果觉得不具体，可以自行画图理解一下。
代码实现如下：
// ac地址：https://leetcode-cn.com/problems/linked-list-cycle-ii/
// 原文地址：https://xxoo521.com/2020-03-03-linked-list-cycle-ii/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
if (!head) return false;
const map = new Map();
let node = head;
map.set(node, true);
while (node.next) {
if (map.get(node.next)) {
return node.next;
}
map.set(node.next, true);
node = node.next;
}
return null;
};
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-03-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录