LeetCode 环形链表快慢指针判断题解

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

解题思路

快慢指针法

定义两个指针分别为 slow，fast，并且将指针均指向链表头节点。
规定，slow 指针每次前进 1 个节点，fast 指针每次前进 2 个节点。
当 slow 与 fast 相等，且二者均不为空，则链表存在环。

为什么有环快慢指针一定相遇

slow 指针每次前进一个节点，故 slow 与 fast 相遇时，slow 还没有遍历完整个链表。设 slow 走过节点数为 s，fast 走过节点数为 2s。设环入口点距离头节点为 a，slow 与 fast 首次相遇点距离入口点为 b，环的长度为 r。则有： s = a + b; 2s = n * r + a + b; n 代表 fast 指针已经在环中循环的圈数。

则推出： s = n * r 意味着 slow 指针走过的长度为环的长度整数倍。

解题

var hasCycle = function (head) {
  let p1 = head;
  let p2 = head;
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) {
      return true;
    }
  }
  return false;
};

时间复杂度：O(n)
空间复杂度：O(1)