如何实现对此链表的排序

Question

所以我需要将数据从最低到最高排序。因此，最低值的指针将指向下一个高点，依此类推。到目前为止，它只指向插入的下一个，而不考虑数据。

我需要对它进行排序，因为每个值都被称为

代码：

def AppendNode(self, node):
if self._isleagl(node):                         #just a error checking method
if self.list_start == None:                 #checks if list is empty
self.list_start = node      
node._set_pointer(None) 
else:                                       #list not empty
item = self.list_start
while item:
if item == node:                    #Checks for duplicates
print("This is not allowed")
elif item._get_pointer() is None:   #If it is end of the List
item._set_pointer(node)
node._set_pointer(None)
break
else:                              #incrimets to the next node via pointer
item = item._get_pointer()

电流输出：

Index   Data   Pointer
0      1       1
1      6       2
2      3       3
3      7      None

期望输出：

Index   Data   Pointer
0      1       2
1      6       3
2      3       1
3      7      None

编辑：

所以我实现了这一点，但它仍然不起作用。我认为这与elif语句本身有关。

elif item.data < node.data:
node._set_pointer(item._get_pointer())
item = item._get_pointer()
break
elif item.data > node.data:
item._set_pointer(node)
item._get_pointer()
break

Answer 1

如果您想按排序顺序维护列表，有时需要将节点插入中间，而不是总是将它们放在最后：

# insert node after item
node.set_pointer(item.get_pointer())  # whatever followed item now follows node
item.set_pointer(node)                # node now follows item

Answer 2

从头开始写这篇文章比修复代码片段更简单——希望一个在实践中展示整个概念的简单演示能帮助您的代码走上正轨。：(

from typing import Optional
class SortedList:
"""A list of ints that keeps itself in sorted order on insert."""
def __init__(self, data: int):
self.data = data
self.next: Optional['SortedList'] = None
def insert(self, data: int) -> 'SortedList':
"""Insert a new node into this list, and return the first node of the list."""
node = SortedList(data)
if node.data < self.data:
# node is now at the head of the list
node.next = self
return node
# Find the list node that will precede the new node.
prev = self
while prev.next is not None and prev.next.data < node.data:
prev = prev.next
# Insert the new node after prev.
node.next = prev.next
prev.next = node
# Self remains the first node of the list.
return self
def print(self) -> None:
"""Print the list starting at this node."""
print(self.data)
if self.next:
self.next.print()
sorted_list = SortedList(9)
sorted_list = sorted_list.insert(6)
sorted_list = sorted_list.insert(1)
sorted_list = sorted_list.insert(3)
sorted_list = sorted_list.insert(7)
sorted_list.print()
# output:
#  1
#  3
#  6
#  7
#  9