Skip to main content
 首页 » 编程设计

python之反转链表并像原来一样显示它

2024年12月31日9java哥

我成功地实现了一个带有打印列表元素的 Display 函数的单链表。我创建了一个迭代反向函数,但显示的列表缺少最后一个元素,而是显示 None。

我多次检查我的算法。有什么我想念的吗?

提前致谢。

class node(object): 
    def __init__(self, data=None): 
        self.data = data 
        self.next = None 
 
class LinkedList(object): 
    def __init__(self, head=None): 
        self.head = node() 
 
    # append to list 
    def append(self, data): 
        new_node = node(data) 
        current = self.head  # head of the list 
        while current.next != None:  # while not last node 
            current = current.next  # traverse 
        current.next = new_node  # append 
 
    def display(self): 
        list = [] 
        current = self.head 
        while current.next != None: 
            current = current.next 
            list.append(current.data) 
        print(list) 
        return 
 
    def reverse(self):  
        current = self.head 
        prev = None 
        while current: 
            next_ = current.next 
            current.next = prev 
            prev = current 
            current = next_ 
        self.head = prev 

测试用例:

list = LinkedList() 
list.append(0) 
list.append(1) 
list.append(2) 
list.append(3) 
list.append(4) 
list.display() 
list.reverse() 
list.display() 

输出:

[0, 1, 2, 3, 4] 
[3, 2, 1, 0, None] 

请您参考如下方法:

问题是由于节点和链表的构造函数,您的链表以空白开头。

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

如果您注意到当您创建一个新的 LinkedList 对象时,您将得到一个没有数据的头部,并且您通过首先获取 self.head.next 来补偿您的打印语句/附加:

current = self.head  # head of the list 
    while current.next != None:  # while not last node 

所以这意味着当你在最后的反向类中设置 self.head 时,你将 head 设置为非空白 head 并且你在打印中跳过它。

为了弥补这一点,您需要创建一个新的空白头并设置在上一个旁边:

    def reverse(self): 
    current = self.head.next 
    prev = None 
    while current: 
        next_ = current.next 
        current.next = prev 
 
        prev = current 
        current = next_ 
 
    #We create a new blank head and set the next to our valid list 
    newHead = node() 
    newHead.next = prev 
    self.head = newHead 

输出是

[0, 1, 2, 3, 4] 
[4, 3, 2, 1, 0]