python - 链表中的有序插入不添加节点

Question

我是 Python 新手。我试图将有序插入编码到链接列表中——以便列表保持升序排列。

但是，我打电话后列表仍然是空的my_linked_list.as_order(1)

我究竟做错了什么？

def as_order(self,x):
    new_node=Node(x)
    if self.head is None or self.head.data < x:
        n=self.head
        new_node.next=n
        n=new_node
    else:
        n=self.head
        while(n.next is not None and n.next.data < x):
            n=n.next
        new_node.next=n.next
        n.next=new_node

标签： pythonlinked-list

Answer 1

您的代码中有两个问题：

• 它从不为 赋值self.head，因此它无法将节点添加到空列表中，或者添加需要成为列表中第一个节点的节点。

• 一旦解决了上一个问题，大于头部值的值将被插入到它之前，这违反了预期的顺序。

两个错误都位于同一个if块中。所以改变这个：

if self.head is None or self.head.data < x:
    n=self.head
    new_node.next=n
    n=new_node

对此：

if self.head is None or self.head.data >= x:  # corrected comparison
    new_node.next = self.head  # (simplification)
    self.head = new_node  # make new node the head