Question

link

Stats

Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is a little tricky, but not difficult. First important thing is to konw what is insertion sort. It is always keeping a sorted list, and then get next unsorted element and insert into correct position of the sorted list.

Solution

Almost all solutions on internet is same, so I will just explain my code. My code can be optimized a little bit by studying this blog, but I guess it’s just refactoring 1 or 2 variables and execution time would not be affected.

My solution is dividing the list into 2 parts: sorted part and unsorted part. I keep getting next node from unsorted and insert into sorted.

My code

Recursion:

public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode sorted = new ListNode(Integer.MIN_VALUE);
    sorted.next = head;
    ListNode unsort = head.next;
    head.next = null;
    // the sorted and unsort both are not null at this point
    while (unsort != null) {
        ListNode pos = sorted;
        ListNode cur = unsort;
        unsort = unsort.next;
        while (pos.next != null && pos.val < cur.val 
            && pos.next.val < cur.val) pos = pos.next;
        // now insert (cur) to (pos.next)
        cur.next = pos.next;
        pos.next = cur;
    }
    return sorted.next;
}

Updated on June 17th, rewrote the code with dummy head. This is different solution, with better readability.

public ListNode insertionSortList(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode dummy = new ListNode(0);
    ListNode cur = head;
    while (cur != null) {
        // insert cur into correct pos
        ListNode pos = dummy;
        while (pos.next != null && pos.next.val < cur.val) {
            pos = pos.next;
        }
        ListNode temp = cur.next;
        cur.next = pos.next;
        pos.next = cur;
        cur = temp;
    }
    return dummy.next;
}