LeetCode 142.环形链表II - JavaScript

题目描述：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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;
};

# 更多资料

若有纰漏，欢迎指正。若对您有帮助，请给个「关注+点赞」，您的支持是我更新的动力 👇

• 📖Blog：剑指 Offer + Leetcode 题解
• 🐱Github ：https://github.com/dongyuanxin/blog
• 🌟 公众号：心谭博客