Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 147] Insertion Sort List



Sort a linked list using insertion sort.


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

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


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.


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


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;