python - 在Python中反转链表

Question

class node:
    def __init__(self, data = None):
        self.data = data
        self.next = None

class linked_list:
    def __init__(self):
        self.head = node()

这就是我在 python 中初始化 LinkedList 数据结构的方法。

在我附加一些节点后，通过执行

my_list.append(1)
my_list.append(2)
my_list.append(3)
my_list.append(4)

并使用我编写的函数显示它，

def display(self):

    elems = []
    curr = self.head

    while curr.next != None:
        curr = curr.next
        elems.append(curr.data)

    print(elems)

它打印出 [1, 2, 3, 4] 看起来不错。

但是，当我尝试使用下面的函数来反转它时

def reverseList(self):

    curr = self.head
    prev = None


    while curr != None:

        curr.next = prev
        prev = curr
        curr = curr.next

    self.head = prev

它给了我一个空的linkedList[]。如果我在纸上绘制 LinkedList，看起来很好，而且我看不出我做错了什么。

Answer 1

反向

看看你的操作顺序:

curr.next = prev
prev = curr
curr = curr.next

在执行 curr = curr.next 之前，curr.next 等于 prev，它等于 None(在第一个过程中) ，以及最终迭代)。

在更改之前，您需要将 curr.next 的值存储在中间变量中。

或者，您可以使用 Python 的多重赋值 ( Multiple assignment and evaluation order in Python ) 在评估所有变量的值后立即为其赋值:

curr.next, prev, curr = prev, curr, curr.next

显示

您在显示功能中也遇到了同样的问题。

while curr.next != None:
    curr = curr.next
    elems.append(curr.data)

您不附加第一个 curr.data，而是直接将 curr 更改为 curr.next。