147. 对链表进行插入排序

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

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

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return null;
        // dummyHead方便在head前插入结点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode lastsort = head,cur = head.next;
        while(cur != null) {
            if (lastsort.val <= cur.val) {
                lastsort = lastsort.next;
            } else {
                // 找到交换结点的前一个结点 pre
                ListNode pre = dummyHead;
                while(pre.next.val <= cur.val) {
                    pre = pre.next;
                }
                lastsort.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            cur = lastsort.next;
        }
        return dummyHead.next;
    }
}