147. 对链表进行插入排序

https://leetcode-cn.com/problems/insertion-sort-list/

解法一：暴力

分两段，有序段和无序（待处理）段。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        work = head.next  #工作指针，无序段第一个结点。紧接在在有序段后面
        #有序段初始，只有[head]
        head.next = None
        Head = ListNode(0)  #辅助头结点
        Head.next = head
        while work:  #每次处理一个，处理完后移，直到末尾
            pre = Head
            p = Head.next
            #在有序段中找合适位置插入
            while p and work.val > p.val:
                pre = p
                p = p.next

            tmp = work
            work = work.next
            pre.next = tmp
            tmp.next = p
            
        return Head.next