java - 链表循环潜在异常

Question

下面是检测链表是否包含循环的代码:

  public static boolean containsCycle(LinkedListNode firstNode) {

// start both runners at the beginning
LinkedListNode slowRunner = firstNode;
LinkedListNode fastRunner = firstNode;

// until we hit the end of the list
while (fastRunner != null && fastRunner.next != null) {
    slowRunner = slowRunner.next;
    fastRunner = fastRunner.next.next;

    // case: fastRunner is about to "lap" slowRunner
    if (fastRunner == slowRunner) {
        return true;
    }
}

// case: fastRunner hit the end of the list
return false;

while循环的条件不应该是fastRunner != null && fastRunner.next.NEXT!= null吗？在目前的代码中，fastRunner可以是链表中的最后一个节点，因此一旦进入while循环，最后一个节点的下一个节点将导致异常。

Answer 1

With the current code, fastRunner can be the very last node in the linked list

fastRunner 不能是链表中的最后一个节点，因为您的 while 循环

while (fastRunner != null && fastRunner.next != null) {

检查fastRunner不是最后一个元素(因为fastRunner.next == null意味着fastRunner是最后一个元素)。您的循环中的此分配

fastRunner = fastRunner.next.next;

当然可以将 fastRunner 设置为 null，但是您没有对它执行任何会导致空指针异常的操作，并且 的下一次迭代while 循环将退出(因为现在 fastRunner == null)