了解如何在链表中找到中间节点的同时循环条件

Question

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

给定一个非空的、带头节点头的单链表，返回链表的中间节点。

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

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

while first and last.next:

但当我这么做的时候，我会收到一个错误

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

条件声明应该是

while last and last.next:

我不明白为什么。下面是带有正确而循环的整个代码：

# 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

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

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

Answer 2

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

初始化将中间（第一个）和结束（最后一个）指针设置为最初唯一知道的内容：列表的开始。循环体将它们向前推进：first=first。下一步向前移动一步，而last=last。下一个下一步向前移动两步。由于last始终位于first之前，因此无需检查first是否可以向前移动。相反，循环的条件检查步进last中使用的两个引用在last和last时是否为非None：。下一步：。

请注意，如果列表有一个元素，last将不会在last之后移动。下一个是无。但是，对于两个元素，last将移动，而first也将移动。结果是满足了从元素数为偶数的列表中选择第二个中间位置的条件。