理解如何找到链表中的中间节点的while循环条件

Question

我不完全理解leetcode上“找到链表的中间”while问题的循环条件：

给定一个具有头节点 head 的非空单链表，返回链表的中间节点。

如果有两个中间节点，则返回第二个中间节点。

对于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

该算法背后的想法是，您不知道列表的末尾在哪里。但是，如果一个指针的步速是另一个指针的两倍，则它会在另一个指针到达中间时到达终点。

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

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