Kata: https://www.codewars.com/kata/linked-lists-insert-sort/train/python


Write an InsertSort() function which rearranges nodes in a linked list so they are sorted in increasing order. You can use the SortedInsert() function that you created in the "Linked Lists - Sorted Insert" kata below. The InsertSort() function takes the head of a linked list as an argument and must return the head of the linked list.

var list = 4 -> 3 -> 1 -> 2 -> null
insertSort(list) === 1 -> 2 -> 3 -> 4 -> null  

If the passed in head node is null or a single node, return null or the single node, respectively. You can assume that the head node will always be either null, a single node, or a linked list consisting of multiple nodes.

My Solution

def insert_sort(head):
    node = head
    while node:
        if node.next and (node.next.data < node.data):
            to_insert = node.next
            node.next = to_insert.next
            head = sorted_insert(head, to_insert.data)  #Inserts a node containing it's second argument at the correct position in the linked list that begins with its first argument.  
        node = node.next
    return head

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.