如何将节点添加到链表？

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:&nbsp; &nbsp; def __init__(self, value):&nbsp; &nbsp; &nbsp; &nbsp; self.value = value&nbsp; &nbsp; &nbsp; &nbsp; self.next = Nonedef insert_ordered(root, data):&nbsp; &nbsp; node = LN(data)&nbsp; &nbsp; if root == None:&nbsp; &nbsp; &nbsp; &nbsp; return node&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; if root.value > data:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.next = root&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp, prev = root, None&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while temp.next and temp.value <= data:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev = temp&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp = temp.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if temp.next == None and temp.value <= data:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp.next = node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.next = prev.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev.next = node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return rootroot = Noneroot = 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