Insertion Sort List

leetcode 147.

Sort a linked list using insertion sort.

Solution. Create a dummyHead. Move the element in head into dummyHead list one by one. The process is like this:

public static ListNode insertionSortList(ListNode head) {
    if (head == null) {
        return head;
    }
    ListNode dummyHead = new ListNode(0);
    while (head != null) {
        // take out head to curr. head move to next
        ListNode curr = head;
        head = head.next;
        // put curr to target position in dummyHead. Put curr between target and target.next
        ListNode target = dummyHead;
        while (target.next != null && target.next.val < curr.val) {
            target = target.next;
        }
        curr.next = target.next;
        target.next = curr;
    }
    return dummyHead.next;
}

Check my code on github.