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

Question

我不完全理解力扣中的“链表的中间结点”问题中 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

- stillearning

---

如果 last 是 None（即你已经到达链表的末尾），那么你应该结束循环。这就是为什么在 last 之前，first 永远不可能等于 None。 - Selcuk

Answer 1

算法的思想是你不知道列表的结尾在哪里。然而，如果你让一个指针的步长是另一个的两倍，当一个指针到达中间时，另一个指针刚好到达结尾。

初始化将中间（first）和结尾（last）指针设置为最初唯一已知的东西：列表的开头。循环体将它们向前移动：first = first.next向前移动一步，而last = last.next.next向前移动两步。由于last始终在first之前，所以无需检查first是否可以向前移动。相反，循环的条件检查用于移动last的两个引用是否都非None：while last and last.next:。

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

- Mad Physicist

Answer 2

把它画出来就很明显了。考虑两个版本：

A - B - C

first / last / last.next
A       B      C  
B       None    

A - B - C - D

first / last / last.next
A       B      C  
B       D      None

- MarkReedZ