按排序顺序在单链表中插入一个整数

Question

我需要定义 insert_in_ascending_order() 方法，但我不知道我在做什么。我需要代码做的是输入：
例如：

8 3 6 2 5 9 4 1 7

并输出：

1 2 3 4 5 6 7 8 9

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, new_node):
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def prepend(self, new_node):
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def insert_after(self, current_node, new_node):
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        elif current_node is self.tail:
            self.tail.next = new_node
            self.tail = new_node
        else:
            new_node.next = current_node.next
            current_node.next = new_node
            
    # TODO: Write insert_in_ascending_order() method
    def insert_in_ascending_order(self, new_node):
        if self.head is None:
            new_node.next = self.head
            self.head = new_node
        elif self.head.data >= new_node.data:
            new_node.next = self.head
            self.head = new_node
        else :
            current = self.head

        current = self.head
        while current is not None:
            print (current.data)
            current = current.next
        new_node = current
        current = new_node

Answer 1

在寻找将成为其后继者的节点时，您需要跟踪将成为您要插入的节点的前任节点。

# start with first node in list
prevNode = None
nextNode = self.head

# find adjacent nodes
while nextNode and nextNode.data < newNode.data:
     prevNode,nextNode = nextNode,nextNode.next

# link to new node
if prevNode: prevNode.next = newNode # insert after
else:        self.head = newNode     # new head

# chain to successor
newNode.next = nextNode
if not nextNode: self.tail = newNode # new tail

Answer 2

您可以让现有的方法为您完成大部分工作。

如果你认为你的头会是最小的值，你的尾巴会是最大的值。您可以从头到尾遍历，直到到达插入点。

如果一开始你处理了一些边缘情况。

    def insert_in_ascending_order(self, new_node):
        # the linked list is empty. just append and return
        if self.head is None:
            self.append(new_node)
            return
    
        # the linked list head value is larger than the current value.
        # meaning our new_node value is the smallest in the list
        # just prepend and return
        if new_node.data < self.head.data:
            self.prepend(new_node)
            return
        
        # now you know can assume everything is sorted
        # and start at the head, your smallest value
        # and move forward from that
        current = self.head
        while True:
            # we've reached our tail.
            # let our append method do the work
            # and break from the loop
            if current.next is None:
                self.append(new_node)
                break
            # we've reached our insert point
            # insert and break
            if new_node.data < current.next.data:
                # make the insert points next, our new_nodes next
                new_node.next = current.next
                # and exchange it with our new_node
                current.next = new_node
                break
            # continue on
            current = current.next

这是完整的代码 repr。

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, new_node):
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
    
    def prepend(self, new_node):
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def insert_in_ascending_order(self, new_node):
        if self.head is None:
            self.append(new_node)
            return
    
        if new_node.data < self.head.data:
            self.prepend(new_node)
            return
        
        current = self.head
        while True:
            if current.next is None:
                self.append(new_node)
                break
            if new_node.data < current.next.data:
                insert_point_next = current.next
                new_node.next = insert_point_next
                current.next = new_node
                break
            current = current.next
    
    def __repr__(self):
        _repr = '['
        current = self.head
        while current is not None:
            _repr = f'{_repr}{repr(current.data)}, '
            current = current.next
        if _repr.endswith(', '):
            _repr = _repr[:-2]
        return f'{_repr}]'

lst = LinkedList()
for i in [8, 3, 6, 2, 5, 9, 4, 1, 7]:
    lst.insert_in_ascending_order(Node(i))
print(lst) # [1, 2, 3, 4, 5, 6, 7, 8, 9]

按排序顺序在单链表中插入一个整数

Inserting an integer in singly-linked list in sorted order

python

linked-list