147. 对链表进行插入排序

147. 对链表进行插入排序

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

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

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

type ListNode struct {
    Val  int
    Next *ListNode
}
func insertionSortList(head *ListNode) *ListNode {
    dummyHead :=&ListNode{Val:  -1}
    var pre *ListNode
    curr := head
    for curr!=nil{
        pre = dummyHead
        next := curr.Next
        // 查找插入位置，从头结点开始遍历，知道当前节点的数据大于插入值停止
        for pre.Next!= nil&&pre.Next.Val<curr.Val{
            pre = pre.Next
        }
        // pre 节点就是需要插入节点位置的前节点
        // 插入一个新的节点
        curr.Next = pre.Next
        pre.Next = curr
        curr = next
    }
    return dummyHead.Next
}