Problem statement

Given the head of a singly linked list, sort it in ascending order using insertion sort, and return the head of the sorted list.

Insertion sort keeps a sorted part that starts empty; at each step it takes the next node of the unsorted input and inserts it at its correct place in the sorted part, until no input remains.

Example 1

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3

Input: head = [2,2,1]
Output: [1,2,2]
Explanation: Equal values simply sit next to each other.

Constraints

• The number of nodes in the list is in the range [1, 5000]
• -5000 <= Node.val <= 5000

Hints for Insertion Sort List

1. Hint 1

   Build the sorted list separately, starting from a dummy node, and move input nodes into it one at a time.

2. Hint 2

   To insert a node, walk the sorted list from the dummy until the next node is larger than the one being inserted.

3. Hint 3

   Remember the input node's next before relinking it — that is where the input continues.

How to solve Insertion Sort List

Keep a sorted list behind a dummy node. Detach each node of the input in turn and splice it in after the last sorted node whose value does not exceed it.

Approach

1. Create dummy (the sorted list starts empty) and set cur = head.
2. While cur is not null: save next = cur.next.
3. Walk prev from dummy while prev.next exists and prev.next.val <= cur.val.
4. Splice: cur.next = prev.next, prev.next = cur; then cur = next.
5. Return dummy.next.

Why it works

The list behind dummy is sorted before each step, and inserting cur after the last node not greater than it keeps it sorted. Every input node is moved exactly once, so at the end the sorted list holds all of them.

Complexity

• Time — O(n²) in the worst case (O(n) for an already sorted list if you first check the last sorted node)
• Space — O(1)

Pitfalls

• Losing the rest of the input by relinking cur before saving cur.next.
• Starting the search from the head of the input rather than the sorted list.
• Using < instead of <= also sorts correctly, but <= keeps equal values in their original order (a stable sort).

Reference solution

Python

from typing import Optional

def insertionSortList(head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    cur = head
    while cur:
        nxt = cur.next
        prev = dummy
        while prev.next and prev.next.val <= cur.val:
            prev = prev.next
        cur.next = prev.next
        prev.next = cur
        cur = nxt
    return dummy.next

Java

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

C++

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

JavaScript

var insertionSortList = function(head) {
    var dummy = new ListNode(0), cur = head;
    while (cur !== null) {
        var nxt = cur.next, prev = dummy;
        while (prev.next !== null && prev.next.val <= cur.val) prev = prev.next;
        cur.next = prev.next;
        prev.next = cur;
        cur = nxt;
    }
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More sorting problems

• Tweet Counts Per Frequency Medium
• Merge Two Sorted Linked Lists in Reverse Order Medium
• Union of Two Linked Lists Medium
• Sort List Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Kth Largest Sum in a Binary Tree Medium