Insertion Sort List

Sort a linked list using insertion sort.

链表的插入排序实现原理很简单， 初始时，sorted list是空，把一个元素一个元素的从原链表中取出来，然后插入到新链表中，在每一次插入过程中，都是找到最合适位置进行插入。时间复杂度为O(n2)，是一种效率并不是很高的算法，但是空间复杂度为O(1)，以高时间复杂度换取了低空间复杂度。代码如下：

# 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 = ListNode(0)
        while head:
            temp = dummy
            nxt = head.next
            while temp.next and temp.next.val < head.val:
                temp = temp.next
            head.next = temp.next
            temp.next = head
            head = nxt
        return dummy.next