python - 了解如何在链表中找到中间节点的 while 循环条件

Question

我不完全理解 "find the middle of linked list" 的 while 循环条件leetcode 问题:

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

对于 while 循环，我认为条件是

while first and last.next:

但是当我这样做时，我收到一条错误消息

AttributeError: 'NoneType' object has no attribute 'next'

条件语句应该是

while last and last.next:

我不明白为什么。这是带有正确 while 循环的完整代码:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def middleNode(self, head):
        first = last = head
        while last and last.next:
            first = first.next
            last = last.next.next
        return first

Answer 1

算法背后的想法是你不知道列表的末尾在哪里。但是，如果您将一个指针以两倍于另一个指针的速度移动，它将在另一个指针到达中间时到达终点。

初始化将中间 (first) 和结尾 (last) 指针设置为您最初知道的唯一内容:列表的开头。循环体使它们向前移动:first = first.next 向前移动一步，而 last = last.next.next 向前移动两步。由于 last 总是在 first 之前，因此无需检查 first 是否可以向前移动。相反，循环的条件检查在步进 last 中使用的两个引用都是非 None:while last 和 last.next: .

请注意，如果列表只有一个元素，last 将不会移动，因为 last.next 为 None。但是，对于两个元素，last 会移动，first 也会移动。结果满足从元素个数为偶数的列表中选取第二个中间的条件。