Insertion Sort List
Problem: Insertion Sort List
The explanation of insertion sort can be found here
Code in Python:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = insert = ListNode(0)
while head:
if insert and insert.val > head.val:
insert = dummy
tmp = head.next
while insert.next and head.val > insert.next.val:
insert = insert.next
head.next, insert.next = insert.next, head
head = tmp
return dummy.next
An important optimization is that when we get a big node which will be definitely inserted at last, we don't need to scan through the whole list to find a position.