Insertion Sort List

medium linked list sorting

Problem

Sort a singly linked list using insertion sort and return the sorted head.

Inputhead = [4, 2, 1, 3]

Output[1, 2, 3, 4]

Maintain a sorted prefix behind a dummy head. For each input node, walk the prefix to its insertion spot and splice in.

list (comma-separated)

def insertion_sort_list(head):
    dummy = ListNode(0)
    cur = head
    while cur:
        nxt = cur.next
        p = dummy
        while p.next and p.next.val < cur.val:
            p = p.next
        cur.next = p.next
        p.next = cur
        cur = nxt
    return dummy.next

function insertionSortList(head) {
  const dummy = { val: 0, next: null };
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    let p = dummy;
    while (p.next && p.next.val < cur.val) p = p.next;
    cur.next = p.next;
    p.next = cur;
    cur = nxt;
  }
  return dummy.next;
}

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0), cur = head;
        while (cur != null) {
            ListNode nxt = cur.next, p = dummy;
            while (p.next != null && p.next.val < cur.val) p = p.next;
            cur.next = p.next;
            p.next = cur;
            cur = nxt;
        }
        return dummy.next;
    }
}

ListNode* insertionSortList(ListNode* head) {
    ListNode dummy(0), *cur = head;
    while (cur) {
        ListNode *nxt = cur->next, *p = &dummy;
        while (p->next && p->next->val < cur->val) p = p->next;
        cur->next = p->next;
        p->next = cur;
        cur = nxt;
    }
    return dummy.next;
}

Explanation

Insertion sort builds a sorted result one node at a time. We keep a growing sorted chain and, for each node from the input, walk that chain to find where it belongs and splice it in. It is the same idea as sorting a hand of cards by inserting each new card into the right spot.

The big helper is a dummy head node, dummy, that sits in front of the sorted chain. Because it is always there, we never have to special-case inserting at the very front — there is always a node before the insertion point to attach to.

For each input node cur, we first save nxt = cur.next so we don't lose the rest of the input after we move cur. Then we start p at dummy and advance while p.next.val < cur.val, stopping at the last node smaller than cur. We splice with cur.next = p.next; p.next = cur, then continue from nxt.

Example: input 4, 2, 1, 3. Insert 4 (chain: 4). Insert 2 before it (2, 4). Insert 1 at the front (1, 2, 4). Insert 3 between 2 and 4 (1, 2, 3, 4).

Finally we return dummy.next, the real head of the sorted list. Each insertion may scan the whole sorted prefix, so the worst case is quadratic time, but it uses no extra memory.

Time: O(n²) Space: O(1)