Insertion Sort List: Sorting a Linked List In Place

May 14, 20265 min read

leetcodeproblemmediumlinked-listssorting

Insertion Sort List is LeetCode problem 147. Given the head of a singly linked list, sort the list using insertion sort and return the sorted list's head.

Example: [4, 2, 1, 3] becomes [1, 2, 3, 4]. Another example: [-1, 5, 3, 4, 0] becomes [-1, 0, 3, 4, 5].

The idea behind insertion sort is to maintain a growing sorted portion. You take each node from the unsorted remainder, find its correct position in the sorted portion, and insert it there.

Each unsorted node is removed and inserted into its correct position in the growing sorted portion.

The approach: dummy head with sorted-portion insertion

The algorithm works by building a new sorted list one node at a time:

Create a dummy head for the sorted portion. This avoids special-case logic when inserting at the front.
Iterate through the original list. For each node, detach it from the unsorted remainder.
Walk the sorted portion to find the correct insertion point. You are looking for the node whose next value is greater than or equal to the current node's value.
Splice the current node in by rewiring next pointers.
Repeat until no unsorted nodes remain.

The dummy head is what makes this clean. Without it, you would need separate logic for the case where the current node belongs at the very front of the sorted list. With the dummy, you always start your search from it, and the first valid insertion point is found naturally.

Practice this pattern

Visual walkthrough

Let's trace through head = [4, 2, 1, 3]. Watch each node get plucked from the unsorted list and inserted into its correct sorted position.

Step 1: Take node 4 from the unsorted list. The sorted list is empty, so 4 becomes the first sorted node.

Sorted: [4]. The dummy head points to 4.

Step 2: Take node 2. Walk the sorted list to find where 2 belongs. 2 < 4, so insert before 4.

Sorted: [2, 4]. Node 2 was inserted at the front (after dummy).

Step 3: Take node 1. Walk the sorted list. 1 < 2, so insert before 2.

Sorted: [1, 2, 4]. Node 1 was inserted at the front (after dummy).

Step 4: Take node 3. Walk the sorted list. 3 > 2 but 3 < 4, so insert between 2 and 4.

Sorted: [1, 2, 3, 4]. Node 3 was spliced in between 2 and 4. Done!

Notice the search pattern. For each node, you walk from the dummy head through the sorted portion until you find where the new value fits. For node 3, that means walking past 1 and 2 (both smaller), then inserting before 4 (the first value that is not smaller). This linear scan through the sorted portion is why the worst case is O(n^2).

The code

Here is the Python solution:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def insertionSortList(head):
    dummy = ListNode(0)
    curr = head

    while curr:
        nxt = curr.next
        prev = dummy

        while prev.next and prev.next.val < curr.val:
            prev = prev.next

        curr.next = prev.next
        prev.next = curr
        curr = nxt

    return dummy.next

Key details:

nxt = curr.next saves the next unsorted node before you detach curr. Once you rewire curr.next during insertion, the link to the rest of the unsorted list would be lost otherwise.
prev = dummy resets the search to the beginning of the sorted list for every node. You always scan from the dummy head forward.
prev.next.val < curr.val finds the correct spot. The inner while loop stops when prev.next is None (meaning curr is the largest so far) or when prev.next.val is greater than or equal to curr.val (meaning curr belongs right after prev).
Two pointer rewires complete the insertion: curr.next = prev.next links curr to the node that was after prev, and prev.next = curr links prev to curr. This splices curr into the sorted chain.

You can add an optimization: if curr.val is greater than or equal to the last sorted node's value, just append it to the end without scanning. This turns already-sorted input into O(n). But the core logic remains the same.

Drill this solution with spaced repetition

Complexity analysis

Metric	Value	Reasoning
Time	O(n^2)	For each of the n nodes, you may scan up to the entire sorted portion (up to n nodes) to find the insertion point. Worst case is reverse-sorted input.
Space	O(1)	Only a fixed number of pointers (`dummy`, `curr`, `nxt`, `prev`) are used. No new nodes are allocated.

Best case is O(n) when the list is already sorted, since each node is immediately appended at the end of the sorted portion (the inner loop does not execute). Average case is O(n^2).

The building blocks

This problem combines two reusable building blocks that show up across many linked list problems.

Linked list insertion

Inserting a node into a specific position in a linked list requires finding the node before the target position, then rewiring two next pointers. The two-line pattern is always the same:

curr.next = prev.next
prev.next = curr

This same splice operation appears in problems like Swap Nodes in Pairs (LeetCode 24) and Reverse Linked List II (LeetCode 92). Once you can perform this reliably, the only question in each problem is where to insert.

Dummy head technique

When building or modifying a linked list, create a dummy sentinel node at the start. This eliminates special-case handling for insertion at the head of the list. You perform all operations relative to the dummy, then return dummy.next as the real head.

In this problem, the dummy head ensures that the inner while loop always has a valid prev node to start from, even when inserting a value smaller than everything currently in the sorted portion.

Edge cases to watch for

Empty list. If head is None, the outer while loop never runs. dummy.next is None, which is returned.
Single node. A list with one node is already sorted. The outer loop runs once, inserts the node after the dummy, and returns it.
Already sorted. Each node's value is greater than or equal to the last sorted node's value, so each insertion happens at the end. The inner loop traverses the full sorted portion each time (unless you add the tail optimization), but the result is still correct.
Reverse sorted. Every node must be inserted at the front of the sorted portion (right after the dummy). The inner loop exits immediately each time, but you still do O(n) outer iterations. This is the worst case for the "skip to end" optimization, but the basic algorithm handles it correctly either way.
Duplicate values. The condition prev.next.val < curr.val (strict less-than) means equal values get inserted after existing nodes with the same value. This preserves the relative order of equal elements, making the sort stable.

From understanding to recall

The insertion sort algorithm on a linked list is a short solution. The core is just a nested loop with two pointer rewires. But under time pressure, the details slip. Which pointer do you reset to dummy on each iteration? Do you save curr.next before or after the insertion? What is the stopping condition for the inner loop?

Reading the solution once gives you understanding. Typing it from scratch, repeatedly, with increasing intervals between sessions, gives you recall. Spaced repetition handles the scheduling so the pattern stays fresh without wasted review sessions.

Try CodeBricks free

Merge Two Sorted Lists - Uses the same dummy head technique to merge two already-sorted lists into one
Partition List - Another linked list problem that builds a result list using dummy heads and pointer rewiring

Visual Learner? Explore how linked list operations work with our Linked List Interactive Visualization.