如何将节点添加到链表？

Question

我正在创建一个接受排序链表和值的函数。我通过 new_node = LN(v) 创建一个具有给定值的新节点。我正在尝试返回一个链表，其中新节点位于正确的位置。该示例将有助于澄清。前任）ll = converts_list_to_linked_list([4, 7, 9, 14]) #我有一个链表：4->7->9->12->14功能：insert_ordered(ll, 12)返回“4->7->9->12->14->None”的链表我完全不知道如何将新节点插入正确的位置。我函数中的最后一个 else 语句不正确。def insert_ordered(ll,x):    new_node = LN(v) #Creates new node    #If given ll is empty, newnode is the linkedlist    if  ll == None:        ll = new_node    #Makes new_node the head of ll if first val is >= new_node value.    elif ll.value >= new_node.value:        temp = ll        ll = new_node        ll.next = temp    #[ERROR] Adds new_node between two nodes of ll in sorted order.     else:        while ll.next != None:            if ll.value < new_node.value:                ll = ll.next                new_node.next = ll.next                ll.next = new_node    return ll迭代求解后，是否可以递归求解？

Answer 1

尝试这个：

class LN:

    def __init__(self, value):

        self.value = value

        self.next = None

def insert_ordered(root, data):

    node = LN(data)

    if root == None:

        return node

    else:

        if root.value > data:

            node.next = root

            return node

        else:

            temp, prev = root, None

            while temp.next and temp.value <= data:

                prev = temp

                temp = temp.next

            if temp.next == None and temp.value <= data:

                temp.next = node

            else:

                node.next = prev.next

                prev.next = node

            return root

root = None

root = insert_ordered(root, 4)

root = insert_ordered(root, 7)

root = insert_ordered(root, 9)

root = insert_ordered(root, 14)

root = insert_ordered(root, 12)

#4->7->9->12->14