链表有环，如何求入环点

题目参考：https://leetcode.cn/problems/linked-list-cycle-ii/description/
题目大致意思为，给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

思路

我们可以利用快慢指针加公式推导得出一个及其简洁的表达式，进而得到答案。

我们设定两个快慢指针，慢指针一次移动一个节点，快指针一次移动两个节点。如果链表有环则必定相遇，且相遇在环内。

我们设定入环点，和首次相遇点：入环点即为环形链表的入口；首次相遇点在环形链表中，是第一次相遇的点。

D：从头节点到入环点的距离
S1：从入环点到首次相遇点的距离
S2：从首次相遇点到入环点的距离

公式推导：首次相遇时慢指针一定还没有走完一个环。
- 相遇时，慢指针走的距离：D + S1
- 假设相遇时快指针已经绕环 n 次，它走的距离：D + n( S1 + S2) + S1
- 因为快指针的速度是 2 倍，所以相同时间走的距离也是 2 倍：D + n ( S1 + S2 ) + S1= 2( D + S1 )即 ( n − 1 ) S1 + n * S2 = D
- 我们不关心绕了几次环，取 n = 1 这种特定情况，消掉 S1：D = S2
利用D = S2求入环点
- 循环过程中，两个指针相遇了，位置相同，可以求出相遇点
- 相遇之后，我们将快指针重置到起点，速度调整为与慢指针一致，一次一个节点，同时出发。
- 由于 D = S2,二者会在入环点相遇，这样就找到我们的入环点了。

代码

var detectCycle = function (head) {
  let slow = head;
  let fast = head;
  while (fast) {
    if (fast.next == null) { // fast.next走出链表了，说明无环
      return null;
    }
    slow = slow.next;        // 慢指针走一步
    fast = fast.next.next;   // 慢指针走一步
    if (slow == fast) {      // 首次相遇
      fast = head;           // 让快指针回到头节点
      while (true) {         // 开启循环，让快慢指针相遇
        if (slow == fast) {  // 相遇，在入环处
          return slow;
        }
        slow = slow.next;
        fast = fast.next;    // 快慢指针都走一步
      }
    }
  }
  return null;
};

拓展 - 寻找重复数

题目链接：https://leetcode.cn/problems/find-the-duplicate-number/description/

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

分析

乍一看，这个题目貌似和链表没有任何关系，但由于索引从 0～n ，值域是 1～n ，值域，在索引的范围内，值可以当索引使。

比如：nums 数组：[4,3,1,2,2]
以 nums[0] 的值 4 作为索引，去到 nums[4]
以 nums[4] 的值 2 作为索引，去到 nums[2]
以 nums[2] 的值 1 作为索引，去到 nums[1]……
从一项指向另一项，将nums数组抽象为链表：4->2->1->3->2。

有环链表，重复数就是入环口，题目就抽象为了，存在重复数就是有环链表，重复数就是入环口。

就下了就十分简单了。

const findDuplicate = (nums) => {
    let slow = 0;
    let fast = 0;
    while (true) {
        slow = nums[slow];
        fast = nums[nums[fast]];   // slow跳一步，fast跳两步
        if (slow == fast) {        // 指针首次相遇
            fast = 0;              // 让快指针回到起点
            while (true) {         // 开启新的循环
                if (slow == fast) {// 如果再次相遇，就肯定是在入口处
                    return slow;   // 返回入口，即重复的数
                }
                slow = nums[slow]; // 两个指针每次都进1步
                fast = nums[fast];
            }
        }
    }
};