链表：当快指针和快指针的下一个节点存在时

Question

链表：当快指针和快指针的下一个节点存在时

3

我正在学习找出链表中间节点的代码：

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

我注意到如果在循环中使用"while fast.next"代替"while fast and fast.next"，结果是相同的。请问我为什么要使用fast和fast.next两个条件来终止while循环？据我理解，如果fast.next是None，那么fast始终是none，这个理解正确吗？

谢谢！

- klme

2

提示：尝试运行 fast=None; print(fast.next)。你认为结果会是什么？ - user202729

1

如果链表中节点数量为偶数，则此代码将会出错。 - Nick ODell

由于您访问了 fast.next.next，您必须检查 fast.next 是否为有效值（非空）。 - Anand Sowmithiran

3个回答

1

当您遍历链表并有一个快指针，它会前进到当前节点的下一个节点的下一个节点时，您必须进行检查。由于最后一个节点将在其next成员变量中具有None（null）值，并且如果仅作为fast.next.next访问，它会导致空指针异常（NPE）。为了避免这种情况，您的循环条件必须像现在一样。

- Anand Sowmithiran

-1

当您遍历的链表数量为奇数时，在最后一个条件判断中，此时快指针指向NULL，然后判断fast->next将导致程序错误。

- Abe

谢谢您的贡献，但我并没有看到对trincot的顶级答案甚至是问题下的评论有任何增值。 - Jan Vítek

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trincot · Accepted Answer

我注意到，如果在循环中使用while fast.next而不是while fast and fast.next，我得到相同的结果。这将适用于具有奇数节点的输入列表，但对于具有偶数节点的输入列表（最简单的例子是空列表），它将失败。

请问为什么我应该同时使用fast and fast.next来停止while循环？

每次迭代都会遍历一对节点，因此在具有偶数个节点的情况下，会出现这样的情况：当评估while条件时，fast为None。如果您只检查fast.next - 而没有先确保fast真正是一个节点 - 它将引发错误，因为这实际上意味着您正在执行None.next，这显然行不通。

从我的理解来看，如果fast.next is None，则fast始终为None，这正确吗？

不，这不正确。如果fast.next is None，则意味着fast是一个拥有next属性的节点，因此fast肯定不是None。但是，在fast为None时，fast.next可能会导致错误。因此，在评估fast.next之前，必须确保fast是一个节点而不是None。

如果条件为fast and fast.next，并且发生fast为None的情况，则评估将短路，并且根本不会评估fast.next（这就是要避免错误的原因）。这是因为当左侧操作数（fast）已经被评估为None时，and操作已经确定将评估为falsy值。