1
\$\begingroup\$

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

Description

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.  
            continue
        node = node.next
    return head
\$\endgroup\$

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.