理解单链队列函数的实现

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的意思是“向前推进一个节点”。