java - 在链表中查找循环

Question

我目前正在使用 Floyd 的循环查找算法来解决一个要求我检测单链表是否包含循环的问题。我了解Tortoise and Hare方法，但对其实现有些困惑。有几篇关于这个算法的帖子，但从来没有针对这个问题的这个方面。

public class Solution {
public boolean hasCycle(ListNode head) {
    
    ListNode slow = head;
    ListNode fast = head; 
    
    while(fast != null) {
        fast = fast.next.next; 
        slow = slow.next; 
        
        if(fast == slow)
            return true; 
    }
    return false;   
}

我的代码中唯一的错误是在我的while循环条件下，我应该有

while(fast != null && fast.next != null)

代替..

while(fast != null) 

但是，后一种 while 循环条件对我来说更有意义。我承认正确的实现只是评估特定节点是否存在，以及该节点是否有后继节点。但是，如果我们只是检查while(fast != null)- 这还不够吗？毕竟，如果fast = null，为什么还要检查fast.next呢？会不会fast = null 存在一个循环存在的情况？没有权利？判断我们是否已经到达链表末尾的标准实现是：while(current != null)- 为什么我们不能在这里这样做？

提前致谢。

Answer 1

但是，如果我们只是检查while(fast != null)- 这还不够吗？

不。

如果您不检查 that fast.nextis not null，那么当您检查时fast.next.next，您可能会得到一个NullPointerException.

（这取决于无循环列表中元素的数量是奇数还是偶数。）

当然，您可以将 移动fast.next != null到循环中……但这只是重新排列代码。效果将是相同的。

Answer 2

尝试使用奇数个元素（例如 5 个）并且没有循环来空运行您的代码。

fast观察到达列表末尾时会发生什么。

Answer 3

您fast = fast.next.next;需要对其进行空检查，fast.next否则您的代码可能会引发空指针异常。

你可以改变

fast = fast.next.next; 

至

if(fast.next != null) fast = fast.next.next;
else break;

您可以通过将此检查保留在循环条目本身来避免额外的代码行。