DSA SheetMedium
EditorialPractice

SORTING › INSERTION SORT

Insertion Sort List

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

a singly linked list divided into a sorted prefix and an unsorted suffixThe drawing shows a dummy node on the far left, followed by a sorted prefix linked from smaller to larger values. The prev pointer marks the last node of that prefix. Immediately after prev is the current node, followed by the unprocessed suffix. The current node is detached from after prev and its link is placed before the first sorted node whose value is at least as large. The dummy node makes the same insertion steps work even when current becomes the new head.dummy25769current = 4nextinsert before 5sorted prefixunsorted suffixprevdetached from unsorted suffix

Approach

  1. Return head immediately when the list has zero or one node, because such a list is already sorted and has no pointer to rearrange.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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

MEASUREBOUNDWHY
TimeO(n^2) worst caseEach 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.
SpaceO(1) extraThe 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.

Common mistakespointer order and the search boundary are the fragile parts

Previous · Insertion Sort Algorithm