LeetCode 147: Insertion Sort List

Problem Restatement

We are given the head of a singly linked list.

Sort the list using insertion sort and return the new head.

Insertion sort builds a sorted output list one node at a time. At each step, it removes one node from the input, finds where it belongs in the sorted part, and inserts it there. LeetCode gives examples such as [4,2,1,3] -> [1,2,3,4] and [-1,5,3,4,0] -> [-1,0,3,4,5].

Examples

Example 1:

head = [4, 2, 1, 3]

Output:

[1, 2, 3, 4]

Example 2:

head = [-1, 5, 3, 4, 0]

Output:

[-1, 0, 3, 4, 5]

Input and Output

Function shape:

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ...

First Thought: Convert to Array

A simple way is:

1. Read all values into an array.
2. Sort the array.
3. Write the sorted values back into the list.

But this does not really implement insertion sort on the linked list. It also modifies values instead of rearranging nodes.

The point of this problem is pointer manipulation.

We should sort by moving nodes.

Key Insight

Maintain a separate sorted linked list.

Process the original list one node at a time.

For each node:

1. Save its next pointer.
2. Find its correct position in the sorted list.
3. Insert it there.
4. Continue with the saved next node.

A dummy node makes insertion at the front easy.

dummy -> sorted nodes

The final sorted head is:

dummy.next

Insertion Example

Input:

4 -> 2 -> 1 -> 3

Start with an empty sorted list:

dummy

Insert 4:

dummy -> 4

Insert 2 before 4:

dummy -> 2 -> 4

Insert 1 before 2:

dummy -> 1 -> 2 -> 4

Insert 3 between 2 and 4:

dummy -> 1 -> 2 -> 3 -> 4

Return dummy.next.

Algorithm

Create a dummy node for the sorted list.

Set curr = head.

While curr exists:

1. Save the next unsorted node:

next_node = curr.next

2. Find the insertion position in the sorted list:

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

3. Insert curr after prev:

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

4. Move to the saved next node:

curr = next_node

Return:

dummy.next

Correctness

The algorithm maintains this invariant:

Before each iteration, the list starting at dummy.next is sorted and contains exactly the nodes already processed from the original list.

Initially, no nodes have been processed, so the sorted list is empty and the invariant holds.

During each iteration, the algorithm takes one unprocessed node curr. It scans the sorted list until it finds the first node with value greater than or equal to curr.val. Inserting curr before that node keeps the sorted order. All previously processed nodes remain in the list, and curr is added exactly once.

Therefore, after the iteration, the sorted list contains exactly all processed nodes and remains sorted.

When the loop finishes, every original node has been processed. By the invariant, dummy.next points to a sorted list containing all original nodes.

Thus, the algorithm returns the sorted linked list.

Complexity

Let n be the number of nodes.

Insertion sort is quadratic in the worst case, which matches the intended algorithm for this problem.

Implementation

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def insertionSortList(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = head

        while curr:
            next_node = curr.next

            prev = dummy

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

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

            curr = next_node

        return dummy.next

Code Explanation

The dummy node anchors the sorted list:

dummy = ListNode(0)

The current pointer walks through the original list:

curr = head

Before moving curr, we save the next original node:

next_node = curr.next

This is important because insertion changes curr.next.

To find the insertion point, start from the dummy node:

prev = dummy

Move forward while the next sorted node is smaller:

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

Insert curr after prev:

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

Then continue with the saved node:

curr = next_node

Finally:

return dummy.next

returns the real head of the sorted list.

Small Optimization

If the input is nearly sorted, we can remember the previous insertion position.

When the next value is larger than the last inserted value, the search can continue from there instead of restarting from the dummy node.

A concise optimized version:

class Solution:
    def insertionSortList(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode(0)
        prev = dummy
        curr = head

        while curr:
            next_node = curr.next

            if prev.val >= curr.val:
                prev = dummy

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

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

        return dummy.next

The simpler version is easier to reason about. The optimized version still has worst-case O(n^2) time.

Testing

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

def build_list(values):
    dummy = ListNode(0)
    curr = dummy

    for value in values:
        curr.next = ListNode(value)
        curr = curr.next

    return dummy.next

def to_list(head):
    result = []
    curr = head

    while curr:
        result.append(curr.val)
        curr = curr.next

    return result

def run_tests():
    s = Solution()

    head = build_list([4, 2, 1, 3])
    assert to_list(s.insertionSortList(head)) == [1, 2, 3, 4]

    head = build_list([-1, 5, 3, 4, 0])
    assert to_list(s.insertionSortList(head)) == [-1, 0, 3, 4, 5]

    head = build_list([1])
    assert to_list(s.insertionSortList(head)) == [1]

    head = build_list([1, 2, 3, 4])
    assert to_list(s.insertionSortList(head)) == [1, 2, 3, 4]

    head = build_list([4, 3, 2, 1])
    assert to_list(s.insertionSortList(head)) == [1, 2, 3, 4]

    head = build_list([2, 2, 1, 1])
    assert to_list(s.insertionSortList(head)) == [1, 1, 2, 2]

    print("all tests passed")

run_tests()

Test meaning: