链表--对于链表进行插入排序（medium）

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4
示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insertion-sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

插入算法

def insertSort(list):
    n = len(list)
    for i in range(n):
        tmp = list[i]
        j = i - 1
        while j >= 0 and list[j] > tmp:
            list[j+1] = list[j] #换值
            j = j - 1
        arr[j+1] = tmp #换值
        print "fin", list,tmp

链表处理是 判断和当前指向的大小，交换

# 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
        """
        if not head:
            return head
        dummy = ListNode(0)
        dummy.next = head
        pre = None
        tmp = None
        cur = head
        while cur and cur.next:
            if cur.val <= cur.next.val:
                cur = cur.next
            else:
                tmp = cur.next
                cur.next = cur.next.next
                pre = dummy
                while tmp.val >= pre.next.val:
                    pre = pre.next
                tmp.next = pre.next
                pre.next = tmp
            
        return dummy.next