Loop in Linked List

链表中的环

问题：给定一个单向链表，如何判断链表中是否有环？

思考

兔子和乌龟要进行一次赛跑 ，他们将在跑道同一位置同时起跑：

1. 如果在直线跑道上  比赛，那么兔子和乌龟最终会分别跑到终点；
2. 如果在圆形跑道上比赛，因为兔子的速度比乌龟快，所以兔子最终会赶上乌龟 。

实现

const hasCycle = function(head) {
  // 如果头节点不存在，或者链表只有头节点，则链表没有环
  if(head === null || head.next === null){
    return false;
  }

  // 慢指针每次移动一步，快指针每次移动两步
  let slow = head.next;
  let fast = head.next.next;

  // 快指针已经到达终点，说明链表没有环
  if(fast === null){
    return false;
  }

  // 每移动一次就检查一遍两个指针是否相遇
  while(slow!==fast){
    // 如果快指针下一步可以到达终点，说明链表没有环
    if(fast.next === null || fast.next.next === null){
      return false;
    }

    // 慢指针向前走一步，快指针向前走两步
    slow = slow.next;
    fast = fast.next.next;
  }

  // 两个指针相遇，说明链表有环
  return true;
};

---

新问题：对于有环单向链表，如何找到的  环的  起点。

思考 

判断链表是否有环的逻辑和上面一样，现在只关注  有环的情况。

假设:

• 经过k步之后两个指针相遇，
• 链表头节点到环的起点的距离为s,
• 环的起到到相遇点的距离为m,
• 环的长度为L

此时:
 慢指针走过的路程为:
D_slow = k = s + m + n₁ * L (n₁为慢指针绕环的次数)

快指针走过的路程为:
D_fast = 2k = s + m + n₂ * L (n₂为快指针绕环的次数)

合并得到s的表达式: s = (n₂ - 2n₁) * L - m

结论

当两个指针相遇时，将其中一个移动到头节点，然后让两个指针一步一步往后走，它们再次相遇的节点就是环起点。

实现

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const detectCycle = function(head) {
  if (!head) return null;
  let slow = head;
  let fast = head;
  let cycle = false;

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      cycle = true;
      break;
    }
  }

  if (cycle) {
    slow = head;
    while (slow !== fast) {
      slow = slow.next;
      fast = fast.next;
    }
    return slow;
  }

  return null;
};