Approach: Insert each node into a sorted prefix

def insertionSortList(self, head):
    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

Complexity: O(n^2) time, O(1) space.

Full Solution — all languages

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def insertionSortList(self, head):
        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

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            ListNode 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;
    }
}

#include <bits/stdc++.h> using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(nullptr) {
    }
};
class Solution {
    public: 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;
    }
};

/** Node shape: { val, next }. Build/return plain objects or use this ctor. */ function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}
/**
 * @param {ListNode} head
 * @return {ListNode}
 */ var insertionSortList = function(head) {
    const dummy = new ListNode(0);
    let cur = head;
    while (cur) {
        const nxt = cur.next;
        let 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;
};

Insertion Sort List

Example 1

Example 2

Constraints