Insertion Sort List

Sort a linked list using insertion sort.

We have explained Insertion Sort at Slide 7 of Arrays

Insertion Sort Wiki has some details on Insertion Sort as well.

Input : 1 -> 3 -> 2

Return 1 -> 2 -> 3

Method1:

Using the same implementation for sorting array.

Solution:

Time: O(n^2)
Space: O(1)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    // 3 2 1
    // 2 3 1
    public ListNode insertionSortList(ListNode A) {
        if (A == null || A.next == null) return A;
        int size = 0;
        ListNode curr = A;
        while (curr != null) {
            size ++;
            curr = curr.next;
        }
        int sortedSize = 1;
        ListNode dummy = new ListNode(0);
        dummy.next = A;
        ListNode unsorted = A.next;
        while (sortedSize < size) {
            ListNode prev = dummy;
            ListNode p = dummy.next;
            ListNode unsortedNext = unsorted.next;
            int s = 0;
            while (s < sortedSize) {
                ListNode next = p.next;
                if (unsorted.val < p.val) {
                    prev.next = unsorted;
                    unsorted.next = p;
                    break;
                }
                prev = p;
                p = next;
                s ++;
                if (s == sortedSize) {
                    prev.next = unsorted;
                }
            }
            unsorted = unsortedNext;
            sortedSize ++;
        }
        ListNode p = dummy;
        int i = 0;
        while (i < size) {
            p = p.next;
            i ++;
        }
        p.next = null;
        return dummy.next;
    }
}

Method 2:

Isolate the node. find the right place & insert. Continue from last sorted node.

Solution 2:

Time: O(n^2)
Space: O(1)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    private ListNode insert(ListNode node, ListNode start, ListNode end) {
        ListNode p = start;
        while (p.next != null && p.next.val < node.val && p != end) {
            p = p.next;
        }
        node.next = p.next;
        p.next = node;
        return p == end ? node : end;
    }
    
    public ListNode insertionSortList(ListNode A) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        ListNode unsorted = A;
        while (unsorted != null) {
            // isolate unsorted
            prev.next = unsorted.next;
            // sorted last node
            prev = insert(unsorted, dummy, prev);
            unsorted = prev.next;
        }
        return dummy.next;
    }
}