Leetcode147.对链表进行插入排序（中等）

插入排序算法：

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

初级解法：

# 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 head is None:
            return head
        head_result = first_result = ListNode(None)
        first_result.next = result = ListNode(head.val)
        head = head.next
        while head != None:
            while result != None and head.val >= result.val:
                result = result.next
                first_result = first_result.next
            if result == None:
                first_result.next = ListNode(head.val)
            else:
                temp = ListNode(head.val)
                first_result.next = temp
                temp.next = result
            first_result = head_result
            result = first_result.next
            head = head.next
        return head_result.next

进阶解法：

# 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(float('-inf'))
        while head:
            p = dummy
            # 链表插排 找到最后一个比head小的节点指向head
            while p.next and p.next.val < head.val:
                p = p.next
            q = head # q替换head head往前走一步
            head = head.next
            p.next, q.next = q, p.next
        return dummy.next