数据结构之环形链表 | 春日游, 杏花吹满头

给定一个链表，判断链表中是否有环。

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

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

提示:

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

示例

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

分析

快慢指针, 慢指针每次移动一步, 快指针每次移动两步, 初始时慢指针指向head, 快指针指向head.next, 如果移动过程中快指针追上慢指针则说明有环, 否则无环

代码

Python3

def hasCircleLinkList (self, head):
  if not head or not head.next:
    return False

  slow = head
  fast = head.next

  while slow != fast:
    if not fast or not fast.next:
      return False
    slow = slow.next
    fast = fast.next.next
  return True

JavaScript

function hasCircleLinkList (head) {
  if (head === null || head.next === null) return false
  let slow = head
  let fast = head.next
  while (slow !== fast){
    if (fast === null || fast.next === null) return false
    slow = slow.next
    fast = fast.next.next
  }
  return true
}

提示

快慢指针时间复杂度为O(N)

• 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次
• 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮

为什么我们要规定初始时慢指针在位置 head，快指针在位置 head.next，而不是两个指针都在位置 head?
由于循环条件一定是判断快慢指针是否重合, 如果我们将两个指针初始都置于 head, 那么 while 循环就不会执行. 我们可以假想一个在 head 之前有一个虚拟节点, 慢指针从虚拟节点移动一步到达 head, 快指针从虚拟节点移动两步到达 head.next, 这样我们就可以使用 while 循环了