Insertion Sort List — Editorial

Opening the reading…

Intuitionthe list is split into a sorted prefix and an unprocessed suffix

Insertion sort keeps two regions: a sorted output prefix and the remaining input suffix. Take the first node from the suffix, find the first sorted node whose value is not smaller, and place the taken node immediately before it. Because the nodes are already linked objects, you can move each node by changing pointers instead of creating a second list or copying values.

The sorted prefix is usually extended at its end, so the next node can be accepted immediately when its value is at least the last sorted value. Only a node that is smaller than that last value needs a search from the beginning. A dummy node sits before the sorted prefix, giving the search a predecessor even when the current node belongs at the new head.

Approach

Return head immediately when the list has zero or one node, because such a list is already sorted and has no pointer to rearrange.

Create a dummy node before head and set prev to the last node known to be in the sorted prefix, because an insertion before head still needs a predecessor pointer.

Set curr to the node after prev and process the suffix one node at a time, because curr is the only node whose final position has not been decided.

If curr->val is at least prev->val, advance both prev and curr, because appending curr preserves sorted order and avoids an unnecessary scan from the dummy node.

Otherwise, scan from the dummy node until scan->next->val is at least curr->val, because scan must remain immediately before the insertion position and the sorted prefix is ordered.

Detach curr with prev->next = curr->next, insert it with curr->next = scan->next and scan->next = curr, then set curr = prev->next, because continuing from the old next node prevents skipping a node or forming a cycle.

Return dummy.next after the suffix is empty, because the first real node may have changed during an insertion at the front.

Complexitythe fast path helps ordered input, but the worst case remains quadratic

MEASURE	BOUND	WHY
Time	O(n^2) worst case	Each node is removed once, but a node that belongs near the front can require scanning many nodes in the sorted prefix. Across a reverse-ordered list, the scan lengths are 1, 2, through n - 1, which sum to O(n^2). Already ordered input takes O(n) because every node uses the append fast path.
Space	O(1) extra	The algorithm keeps only a dummy node and a constant number of ListNode pointers; it reuses every original link. The returned list is required output and is excluded from the extra-space bound. The bound stays O(1) for every input shape.

Here n is the number of nodes in the input list.

Annotated solutionC++ · in-place linked-list insertion sort

CPPMove each node into the sorted prefix, using the tail check to skip needless searches.

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode dummy(0);
        dummy.next = head;

        ListNode* prev = head;
        ListNode* curr = head->next;

        while (curr != nullptr) {
            if (curr->val >= prev->val) {
                prev = curr;
                curr = curr->next;
            } else {
                ListNode* scan = &dummy;
                while (scan->next->val < curr->val) {
                    scan = scan->next;
                }

                prev->next = curr->next;
                curr->next = scan->next;
                scan->next = curr;
                curr = prev->next;
            }
        }

        return dummy.next;
    }
};

The three pointer assignments in the insertion branch must be read as one operation. First prev skips over curr, removing it from its old position. Then curr points to the node that used to follow scan. Finally scan points to curr, placing it into the sorted prefix. The last assignment to curr resumes at the next unprocessed node; prev deliberately stays where it is because the inserted node is before it.