Понимание реализации функции односвязной очереди

Question

У меня есть следующая проблема, показанная здесь: Я не уверен, почему этот ответ правильный, или даже как визуализировать выполнение этой функции.Как вычисляется выражение множественного присваивания, показанное в цикле while?

Answer 1

Множественное присваивание похоже на одно присваивание, но все сразу - вы можете предоставить кортеж значений и назначить кортеж значений одинаковой длины, все сразу:

a, b, c = 1, 2, 3
a == 1  # True
b == 2  # True
c == 3  # True

Итак, вот чтофункция выполняет:

def reverse(self):
    p, q = self.head, self.head.next  # initialize p and q as first two elements of queue
    while q:  # iterate until q is None (that is, until we reach the end of the list)
              # This indicates that we will need to have a way for q to advance
              #   towards the end of the list. Presumably we'll be setting q as
              #   something that will eventually be None.
              # We know that the `next` of the last element in the list will be
              #   None, so that's a good starting point.
        _____________________  # blank line to fill in
    self.head, self.tail = self.tail, self.head  # swap head and tail of list with each other
    self.tail.next = None  # set the next element of the tail to None, as it should be.

Итак, что же происходит в пустом?Что ж, мы можем выяснить, на что каждая отдельная переменная должна измениться.Подход, который мы будем использовать, состоит в том, чтобы изменить направление каждого элемента, с которым мы сталкиваемся - вместо .next, указывающего на следующий элемент, мы сделаем так, чтобы он указывал на предыдущий элемент.Таким образом, мы бы хотели

q.next = p

, поскольку q является вторым элементом в списке, а p является элементом, который предшествует ему.Затем мы просто хотим перейти p и q к следующим двум элементам в списке:

p = q
q = q.next

Обычно, если бы мы делали это в отдельных операторах, нам понадобилась бы временная переменная длясохранить значение q.next - но множественное присваивание позволяет обойти это:

q.next, p, q = p, q, q.next

В конце процесса, перевернув все ссылки между элементами , мы просто перевернемголова и хвост.И установите self.tail.next на None, так как self.tail - это элемент, который использовал , чтобы быть self.head, и мы изначально его пропустили.

Answer 2

Как только вы визуализируете односвязный список на бумаге в виде списка, ну, вы заметите, что на каждой итерации все, что он делает, это восстанавливает соединение:

initial setup:

(1) -> (2) -> (3) -> (4) -> (5) -> nil
 p      q


step 1:

(1) <- (2) -> (3) -> (4) -> (5) -> nil
        p      q


step 2:

(1) <- (2) <- (3) -> (4) -> (5) -> nil
               p      q


step 3:

(1) <- (2) <- (3) <- (4) -> (5) -> nil
                      p      q


step 4:

(1) <- (2) <- (3) <- (4) <- (5)    nil
                             p      q

Здесь

• q.next = p означает «перевернуть соединение»;
• p, q = q, q.next означает «продвинуться на один узел вперед».