Skip to main content
 首页 » 编程设计

python之在 python 中反转链表

2025年01月19日9zhoujg

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

请您参考如下方法:

反转

查看你的操作顺序:

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。