# 0147. Insertion Sort List
###### tags: `Leetcode` `Medium` `Sort`
Link: https://leetcode.com/problems/insertion-sort-list/description/
## Code

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyNode = new ListNode(-5001);
        ListNode cur = head;
        ListNode pre = dummyNode;
        ListNode next = null;
        while(cur!=null){
            next = cur.next;
            //find the right position to insertionSortList
            while(pre.next!=null && pre.next.val<cur.val){
                pre = pre.next;
            }
            //insert between pre and pre.next
            cur.next = pre.next;
            pre.next = cur;

            pre = dummyNode;
            cur = next;
        }
        return dummyNode.next;
    }
}