I'm creating a function that takes in a sorted linked list and a value. I create a new node with the given value by new_node = LN(v). I am trying to return a linked list with the new node in the correct position. The example will help clarify.
Ex)
ll = converts_list_to_linked_list([4, 7, 9, 14]) #I have a linked list: 4->7->9->12->14
The Function:
insert_ordered(ll, 12)
returns a linked list of "4->7->9->12->14->None"
I am completely stuck on how to insert the new node in the correct position. The last else statement in my function is incorrect.
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
After solving this iteratively, is it possible to solve it recursively?
Try this:
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