了解如何在链接lis中查找中间节点的while循环条件

Question

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

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 and last.next:。你知道吗

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

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