在快速和慢速指针问题中,为什么要检查 fast.next 而我们为什么不检查 fast.next.next

In Fast and Slow Pointer problems, why check for fast.next and why are we not checking fast.next.next

我在看LeetCode问题141. Linked List Cycle:

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

我看到了这个解决方案:

function hasCycle(head) {
    let fast = head
    let slow = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if (fast == slow) return true
    }
    return false
}

为什么它检查 fast.next 而我们为什么不检查 fast.next.next

需要进行的检查是为了避免执行某些计算结果为 (null).next 的操作,这会引发错误。

如果您随后查看循环体,您会看到我们执行 fast = fast.next.next,因此有两次访问 next。我们需要确保这些访问不是针对 null 值进行的。因此,我们应该检查:

  • fast.next 中我们没有 fast 等于 null
  • 当之前的检查没问题时,在 fast.next.next 中我们没有 fast.next 等于 null

这应该可以解释为什么 while 情况是这样的。

无需检查 fast.next.next 不是 null,因为该级别的 null 不会触发错误。这只是意味着在循环的迭代中,fast 将被设置为 null,但这是一个有效的操作。