LeetCode 147 - Insertion Sort List

LeetCode Problem 147

Difficulty: 🟡 Medium
Topics: Linked List, Sorting

Solution

Problem Understanding

The problem asks us to sort a singly linked list using the insertion sort algorithm. Unlike array sorting problems where elements can be accessed directly by index, linked lists require sequential traversal, so insertion operations behave differently and require careful pointer manipulation.

The input is the head node of a singly linked list. Each node contains an integer value and a pointer to the next node. The goal is to rearrange the nodes so that the resulting linked list is sorted in ascending order, then return the head of the sorted list.

Insertion sort works by maintaining a growing sorted portion of the data. At each step, one element is taken from the unsorted portion and inserted into the correct position within the sorted portion. For arrays, this often involves shifting elements. For linked lists, insertion becomes more natural because nodes can be relinked without shifting memory.

The constraints tell us that the list contains between 1 and 5000 nodes. This is small enough that an O(n²) algorithm is acceptable, which is important because insertion sort naturally runs in quadratic time in the worst case. Node values range from -5000 to 5000, so negative numbers and duplicates must both be handled correctly.

Several edge cases are important to consider:

• A list with only one node is already sorted.
• An already sorted list should remain unchanged.
• A reverse sorted list represents the worst case for insertion sort because every new node must be inserted at the beginning.
• Duplicate values must preserve valid ordering.
• Negative values must be handled naturally alongside positive values.
• Insertions at the head of the sorted portion are especially easy to mishandle if pointer updates are incorrect.

Because this is a singly linked list, we cannot move backward. That means each insertion requires scanning from the beginning of the sorted portion to find the correct insertion point.

Approaches

Brute Force Approach

One straightforward solution is to extract all node values into an array, sort the array using a standard sorting algorithm, then rebuild the linked list using the sorted values.

This approach works because arrays support efficient sorting operations through built-in algorithms like Timsort in Python or sort.Ints in Go. Once the values are sorted, reconstructing the linked list produces the correct final ordering.

However, this method ignores the main intent of the problem, which is implementing insertion sort directly on a linked list. It also requires additional memory proportional to the number of nodes because all values must be copied into an auxiliary array.

Optimal Approach

The better solution is to perform insertion sort directly on the linked list itself.

The key insight is that linked lists are naturally suited for insertion operations. In an array, inserting an element in the middle requires shifting many elements. In a linked list, insertion only requires pointer updates once the insertion position is found.

We maintain a separate sorted list and iterate through the original list one node at a time. For each node:

1. Remove it from the original traversal.
2. Find the correct position in the sorted list.
3. Insert it into that position.

A dummy node is extremely useful here because it simplifies insertion at the beginning of the list. Without a dummy node, inserting before the current head would require special handling.

Although the time complexity is still O(n²), this is the intended insertion sort implementation and uses only O(1) extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Copy values into array, sort array, rebuild list
Optimal	O(n²)	O(1)	Perform insertion sort directly on the linked list

Algorithm Walkthrough

Optimal Linked List Insertion Sort

1. Create a dummy node that acts as the head of the sorted list.

The dummy node simplifies insertion logic, especially when a node must be inserted at the very beginning of the sorted list. 2. Start traversing the original list using a pointer called current.

This pointer represents the node we are currently inserting into the sorted portion. 3. Save the next node before modifying pointers.

Since insertion changes the current node’s next pointer, we must preserve access to the remainder of the original list. 4. Find the insertion position inside the sorted list.

Start from the dummy node and move forward until reaching the first node whose value is greater than the current node’s value. 5. Insert the current node into the sorted list.

Perform the insertion using standard linked list pointer manipulation:

• current.next = prev.next
• prev.next = current

6. Move to the next node from the original list.

Continue processing until every node has been inserted into the sorted portion. 7. Return dummy.next.

The dummy node itself is artificial, so the real sorted list begins after it.

Why it works

The algorithm maintains an invariant that the list starting at dummy.next is always sorted after each iteration.

Initially, the sorted list is empty, so the invariant trivially holds. During each iteration, one node is inserted into its correct position within the already sorted portion. Because insertion occurs in sorted order, the invariant remains true after every step.

After all nodes are processed, every node belongs to the sorted list and the entire linked list is sorted.

Python Solution

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

from typing import Optional

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

        while current:
            next_node = current.next

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

            current.next = prev.next
            prev.next = current

            current = next_node

        return dummy.next

The implementation begins by creating a dummy node. This node serves as the stable entry point for the sorted portion of the list.

The current pointer traverses the original linked list one node at a time. Before inserting the node into the sorted list, the code stores current.next in next_node. This is necessary because insertion rewires the next pointer.

The inner loop searches for the insertion point. The pointer prev starts at the dummy node and advances until it finds the correct location where the current node should be inserted.

Once the correct insertion position is identified, the node is inserted by adjusting pointers. First, current.next is pointed to the node after prev. Then prev.next is updated to point to current.

Finally, traversal continues using the saved next_node.

Because every insertion preserves sorted order, the final linked list returned from dummy.next is fully sorted.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    dummy := &ListNode{}
    current := head

    for current != nil {
        nextNode := current.Next

        prev := dummy
        for prev.Next != nil && prev.Next.Val < current.Val {
            prev = prev.Next
        }

        current.Next = prev.Next
        prev.Next = current

        current = nextNode
    }

    return dummy.Next
}

The Go implementation follows exactly the same algorithmic structure as the Python solution. The main difference is explicit pointer syntax.

Go uses nil instead of None, and linked list nodes are manipulated through pointers directly. The dummy node is allocated using &ListNode{}.

Since Go does not provide automatic optional typing like Python, all linked list references are handled explicitly through *ListNode.

No integer overflow concerns exist here because node values are constrained to a small range.

Worked Examples

Example 1

Input:

4 -> 2 -> 1 -> 3

Initial state:

Sorted: empty
Current: 4

Step	Current Node	Sorted List After Insertion
1	4	4
2	2	2 -> 4
3	1	1 -> 2 -> 4
4	3	1 -> 2 -> 3 -> 4

Final output:

1 -> 2 -> 3 -> 4

Detailed trace:

1. Insert 4 into empty sorted list.
2. Insert 2 before 4.
3. Insert 1 before 2.
4. Insert 3 between 2 and 4.

Example 2

Input:

-1 -> 5 -> 3 -> 4 -> 0

Step	Current Node	Sorted List After Insertion
1	-1	-1
2	5	-1 -> 5
3	3	-1 -> 3 -> 5
4	4	-1 -> 3 -> 4 -> 5
5	0	-1 -> 0 -> 3 -> 4 -> 5

Final output:

-1 -> 0 -> 3 -> 4 -> 5

The important operation occurs during insertion of 0. The algorithm scans the sorted list and inserts 0 between -1 and 3.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each insertion may scan the entire sorted portion
Space	O(1)	Sorting is done in-place with only a few pointers

The outer loop processes each node exactly once. For every node, the algorithm may need to scan through the already sorted portion of the list to find the insertion point.

In the worst case, such as a reverse sorted list, the number of comparisons becomes:

1 + 2 + 3 + ... + (n - 1)

This sums to O(n²).

The algorithm uses only a constant number of extra pointers regardless of input size, so auxiliary space complexity is O(1).

Test Cases

# Definition for testing
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

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

    return dummy.next

def to_list(head):
    result = []

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

    return result

class Solution:
    def insertionSortList(self, head):
        dummy = ListNode(0)
        current = head

        while current:
            next_node = current.next

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

            current.next = prev.next
            prev.next = current

            current = next_node

        return dummy.next

solution = Solution()

# Example 1
head = build_list([4, 2, 1, 3])
assert to_list(solution.insertionSortList(head)) == [1, 2, 3, 4]  # basic unsorted case

# Example 2
head = build_list([-1, 5, 3, 4, 0])
assert to_list(solution.insertionSortList(head)) == [-1, 0, 3, 4, 5]  # negatives and mixed ordering

# Single element
head = build_list([1])
assert to_list(solution.insertionSortList(head)) == [1]  # minimal input size

# Already sorted
head = build_list([1, 2, 3, 4, 5])
assert to_list(solution.insertionSortList(head)) == [1, 2, 3, 4, 5]  # no reordering needed

# Reverse sorted
head = build_list([5, 4, 3, 2, 1])
assert to_list(solution.insertionSortList(head)) == [1, 2, 3, 4, 5]  # worst-case insertion order

# Duplicate values
head = build_list([3, 1, 2, 1, 3])
assert to_list(solution.insertionSortList(head)) == [1, 1, 2, 3, 3]  # duplicates handled correctly

# All identical values
head = build_list([7, 7, 7, 7])
assert to_list(solution.insertionSortList(head)) == [7, 7, 7, 7]  # repeated equal values

# Negative values only
head = build_list([-3, -1, -2, -5])
assert to_list(solution.insertionSortList(head)) == [-5, -3, -2, -1]  # all negative numbers

# Large gap values
head = build_list([1000, -1000, 500, 0])
assert to_list(solution.insertionSortList(head)) == [-1000, 0, 500, 1000]  # wide numeric range

Test	Why
[4,2,1,3]	Validates standard unsorted input
[-1,5,3,4,0]	Ensures negative and positive values work together
[1]	Tests smallest possible input
[1,2,3,4,5]	Verifies already sorted lists remain unchanged
[5,4,3,2,1]	Tests worst-case insertion behavior
[3,1,2,1,3]	Validates handling of duplicate values
[7,7,7,7]	Ensures identical values do not break ordering
[-3,-1,-2,-5]	Tests negative-only sorting
[1000,-1000,500,0]	Confirms large value ranges work correctly

Edge Cases

Single Node List

A linked list containing only one node is already sorted. This case can sometimes expose bugs where pointer manipulation assumes the existence of additional nodes. In this implementation, the loop runs once, inserts the node into the sorted list, and terminates correctly.

Reverse Sorted List

A reverse sorted list such as 5 -> 4 -> 3 -> 2 -> 1 is the worst-case scenario for insertion sort. Every new node must be inserted at the beginning of the sorted list. Incorrect handling of head insertion often causes broken links or lost nodes. The dummy node ensures these insertions are handled uniformly and safely.

Duplicate Values

Lists containing duplicates can be problematic if insertion conditions are written incorrectly. For example, using <= instead of < changes insertion ordering behavior. This implementation uses:

while prev.next and prev.next.val < current.val:

This guarantees that duplicates are inserted consistently while preserving valid sorted order.

Insertion at the Beginning

When the current node is smaller than all nodes already in the sorted list, it must become the new first element. Without a dummy node, this requires special-case logic to update the head pointer. The dummy node eliminates this complexity by making every insertion follow the same pointer update pattern.