147. Insertion Sort List

class Solution {   //难需要背过
    public ListNode insertionSortList(ListNode head) {
        if(head==null || head.next == null) return head;
        ListNode cur = head;
        ListNode sorted = new ListNode(0);
        ListNode pre = sorted;
        ListNode next = null;
        while(cur!=null){
            next = cur.next;
            while(pre.next!=null && pre.next.val < cur.val)
                pre = pre.next;
            cur.next = pre.next;
            pre.next = cur;
            pre = sorted;
            cur = next;
        }
        return sorted.next;
    }
}