142 Linked List Cycle II

142. Linked List Cycle II

解：https://leetcode.cn/problems/linked-list-cycle-ii/solutions/12616/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-

slow慢指针走了s步，fast快指针走了f步

根据：

f = 2s （快指针每次2步，路程刚好2倍）
f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb (s走的步数刚好是n倍的环长)

从head结点走到入环点需要走： a + nb，而slow已经走了nb，那么slow再走a步就是入环点了。

如何知道slow刚好走了a步？从head开始，和slow指针一起走，相遇时刚好就是a步

为什么走a步之后会相遇：

入口为 a + nb，当n = 0时和 n属于正整数时都表示环的入口。

My solution:

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let slow = head,
    fast = head
  if (!(fast && fast.next)) {
    // 特判空链表及只有一个元素的链表
    return null
  }
  while (fast && fast.next) {
    // 找到相遇点， fast 和 slow 指针分别走了 2n，n 个环的周长。
    fast = fast.next.next
    slow = slow.next
    if (fast === slow) {
      break
    }
  }
  if (fast !== slow) {
    // 无环
    return null
  }
  fast = head
  while (fast !== slow) {
    // fast 和 slow共同走a步，之后在入口相遇
    slow = slow.next
    fast = fast.next
  }
  return slow
}

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let slow = head,
    fast = head
  while (true) {
    if (!(fast && fast.next)) {
      return null
    }
    slow = slow.next
    fast = fast.next.next
    if (fast === slow) {
      break
    }
  }
  fast = head
  while (fast !== slow) {
    fast = fast.next
    slow = slow.next
  }
  return slow
}