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，它看起来很好，我看不出我做错了什么。

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。