# (Codewars) Linked Lists-Sorted Insert

## 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_j = head
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


## 1 Answer

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):
if head is None:
return Node(data)
if data < head.data:
new_head = Node(data)
new_head.next = head
return new_head
# at this point we will always return head
current_node = 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
return head


This is an improvement over the code you presented because it separates special cases from traversal.

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.

This simplification allows us to eliminate a variable at the cost of a somewhat more difficult to understand loop condition. Overall this tradeoff is worth it, because we reduce the complexity of the loop body.

After we found the insertion position, the insertion itself becomes a matter of setting the properties in the correct order to avoid dropping the tail of the list.