21-05-20-环形链表第一个环的入口点

题目地址

https://leetcode-cn.com/problems/linked-list-cycle-ii/

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 进阶： 你是否可以使用 O(1) 空间解决此题？

思路

思路1

• map 存储节点，然后判断重复，空间复杂度是 O(N)，比较简单就忽略代码了。

思路2

• 快慢指针，快指针从头节点每次步进两个节点，慢指针从头节点每次步进一个。
• 快指针每次步进都检测是否为 null 和是否等于 head，等于 head 返回 head，等于 null 表示没有环。
• 当快慢指针第一次相遇后，快指针重新指向 head。
• 快慢指针分别步进一个节点，当两个指针相遇的时候就是第一个环的入口点。

证明一下思路2，为什么呢？

我们使用两个指针，fast与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

如下图所示，设链表中环外部分的长度为a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为

a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的2倍。因此，我们有

a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了a=c+(n-1)(b+c)a=c+(n−1)(b+c)的等量关系，我们会发现：从相遇点到入环点的距离加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针head。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
  if (!head || !head.next) return null;
  let slow = head;
  let fast = head;
  while (slow != fast || fast == head) {
    if (fast.next != null) {
      fast = fast.next.next;
    } else {
      return null;
    }
    slow = slow.next;
    if (fast == head) return head; // 回环
    if (fast == null) return null; // 空了就没有环
  }
  fast = head;
  while (slow != fast) {
    fast = fast.next;
    slow = slow.next;
  }
  return slow;
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)