(Codewars) Linked Lists-Sorted Insert

Question

Kata: https://www.codewars.com/kata/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

• Solomon Ucko: 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.

Answer 1

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.