Понимание условия цикла while как найти средний узел в связанном списке

Question

Я не совсем понимаю условие цикла while для "найти середину связанного списка" вопрос по коду leetcode:

Учитывая непустое,односвязный список с заголовком главного узла, возвращает средний узел связанного списка.

Если имеется два средних узла, возвращает второй средний узел.

Для цикла 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