前端之家

  1. 首页
  2. 问答

如何实现对此链表的排序？

• 问答

所以我需要将数据从最低到最高排序。因此，最低值的指针将指向下一个最高的指针，依此类推。到目前为止，无论数据如何，它都指向插入的下一个。

我需要在附加每个值时对其进行排序

代码：

    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
wzhm123456 回答：如何实现对此链表的排序？

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

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

从头开始编写此代码比尝试修复代码片段更简单-希望一个简单的演示在实践中展示整个概念，有助于使您的代码步入正轨。 ：）

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
linked-listoopsorting
本文链接：https://www.f2er.com/3161667.html

大家都在问