## Description

Write a SortedInsert() function which inserts a node into the correct location of a pre-sorted linked list which is sorted in ascending order. SortedInsert takes the head of a linked list and data used to create a node as arguments. SortedInsert() should also return the head of the list.

sortedInsert(1 -> 2 -> 3 -> null, 4) === 1 -> 2 -> 3 -> 4 -> null)
sortedInsert(1 -> 7 -> 8 -> null, 5) === 1 -> 5 -> 7 -> 8 -> null)
sortedInsert(3 -> 5 -> 9 -> null, 7) === 3 -> 5 -> 7 -> 9 -> null)


## My Solution

def sorted_insert(head, data):
prev = None
node_i = Node(data)
while node_j:
if node_j.data > data:
node_i.next = node_j
break
prev = node_j
node_j = node_j.next
else:
node_i.next = None
if prev:
prev.next = node_i
return head if prev else node_i

• FWIW, a binary search tree (or a balanced binary search tree, which is a more complicated but better performing subtype) may be better for this sort of thing when it's an option. Mar 10, 2019 at 1:14

First some minor issues with naming, then a rewrite:

prev could be previous, there is no need to skimp on characters. node_j and node_i are completely different things, yet their names suggest they are both "moving pointers". That is only true for node_j. May I suggest using current and insert instead?

The use of while..else is pretty cool, but confused me at first. Take that with a grain of salt, though, I'm not usually writing a lot of python.

Now for the meat of the problem:

This can be simplified by inverting the logic on your traversal. Consider the following code:

def sorted_insert(head, data):
return Node(data)
# at this point we will always return head
# advance if next node is smaller than node to be inserted
while current_node.next is not None and current_node.next.data < data:
current_node = current_node.next

insert = Node(data)
insert.next = current_node.next
current_node.next = insert

1. We first handle the special case of an empty list (head is None).
2. Then we handle the case where we create a new head (data < head.data)
With these special cases out of the way we now search for the insertion position, namely what you store in prev. The way this works is by advancing current_node only if the next node also has a smaller data than the insertion.