如何将节点添加到链表?

Question

我正在创建一个函数，该函数接收排序的链表和值。我通过 new_node = LN(v( 创建一个具有给定值的新节点。我正在尝试返回一个新节点位于正确位置的链表。该示例将有助于澄清。

例(

ll = converts_list_to_linked_list([4， 7， 9， 14]( #I 有一个链表： 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