Pengjielee's blog

题目

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

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

进阶：

你是否可以使用 O(1) 空间解决此题？

示例：

示例 1：
3 -> 2 -> 0 -> -4 -> 2

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
1 -> 2 -> 1

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
1 -> null
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/linked-list-cycle-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

假设链表环前有 a 个节点，环内有 b 个节点。

本题核心思路：走 a+nb 步一定处于环的入口位置

1. 利用快慢指针 fast 和 slow，fast 一次走两步，slow 一次走一步；
1. 当两个指针第一次相遇时，假设 slow 走了 s 步，下面计算 fast 走过的步数；
- i. fast 比 slow 多走了 n 个环：f = s + nb；
- ii. fast 比 slow 多走一倍的步数：f = 2s –> 跟上式联立（2s = s + nb）可得 s = nb；
- iii. 综上计算得，f = 2nb，s = nb；
- 也就是两个指针第一次相遇时，都走过了环的倍数，那么再走 a 步就可以到达环的入口；（为什么再走a步就到环的入口？）
1. 让 fast 从头再走，slow 留在原地，fast 和 slow 均一次走一步，当两个指针第二次相遇时，fast 走了 a 步，slow 走了 a+nb 步；
1. 此时 slow 就在环的入口处，返回 slow；

作者：edelweisskoko 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/142-huan-xing-lian-biao-iishuang-zhi-zhe-k8ju/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

为什么再走a步就到环的入口？

1. 如果让指针从链表头部一直向前走并统计步数k，那么所有走到链表入口节点时的步数是：k=a+nb（先走 a 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点）。
1. 而目前，slow 指针走过的步数为 nb 步。因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口。
1. 但是我们不知道 a 的值，该怎么办？依然是使用双指针法。我们构建一个指针，此指针需要有以下性质：此指针和slow 一起向前走 a 步后，两者在入口节点重合。那么从哪里走到入口节点需要 a 步？答案是链表头部head。

作者：jyd 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

JS实现

1、哈希表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  const map = new Map();
  let node = head;
  while (node != null) {
    if (map.has(node)) {
      return node;
    } else {
      map.set(node, true);
    }
    node = node.next;
  }
  return null;
};

2、快慢指针

var detectCycle = function (head) {
  // 定义快慢指针
  let fast = head,
    slow = head;

  while (true) {
    //如果快指针一直走到链表末端，说明链表无环，返回null
    if (fast === null || fast.next === null) {
      return null;
    }
    // 慢指针走一步
    slow = slow.next;
    // 快指针走两步
    fast = fast.next.next;
    // 第一次相遇，退出循环
    if (slow === fast) {
      break;
    }
  }
  // 快指针回到链表头
  fast = head;
  // 快慢指针一起走
  while (slow != fast) {
    fast = fast.next;
    slow = slow.next;
  }
  return slow;
};