链表循环潜在异常

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

使用当前代码，fastRunner 可以是链表中的最后一个节点

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

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

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

fastRunner = fastRunner.next.next;

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

Answer 2

这个算法当然是正确的，只要线程安全不是问题。 换句话说，如果在此方法运行时由另一个线程中的代码更改列表，那么它肯定会产生不正确的结果或NullPointerException。

但是，如果您的代码是单线程的，则NullPointerException永远不会发生。 要使此代码抛出NullPointerException，必须有一个.运算符，其左侧有一个 null 值。 尽管有其他类型的代码可以抛出NullPointerException，例如自动取消装箱空值，以及在 for-each 循环中使用空参数;你没有这些。

所以要看到这段代码可以抛出一个NullPointerException，你应该依次考虑代码中的每个.运算符。 有四个点需要考虑。

1. while (fastRunner != null && fastRunner.next != null) {中的点 - 这永远不会引起NullPointerException，因为只有在fastRunner不为空时才检查此代码，这要归功于短路评估。
2. slowRunner = slowRunner.next;中的点 - 这永远不会引起NullPointerException，因为slowRunner取的每个值都已经被fastRunner或fastRunner.next取了。因此，如果slowRunner为空，则您已经得到了NullPointerException。 你不能从这个点得到它。
3. fastRunner = fastRunner.next.next;中的第一个点 - 这永远不会引起NullPointerException，因为您已经检查了fastRunner不为空。
4. fastRunner = fastRunner.next.next;中的第二个点 - 这永远不会引起NullPointerException，因为您已经检查了fastRunner.next不为空。

因此，您的代码中没有任何可能导致NullPointerException，除非在执行代码时由第二个线程更改列表。