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

Question

我不完全理解为对本文给出的while问题"find the middle of linked list"循环条件：

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

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

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

该算法背后的想法是，你不知道在哪里列表的到底是什么。不过，如果你快一步一个指针的两倍，另外，它会到达终点，就像其他到达中间。

初始化设置中（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