(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

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.