> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Insertion Sort List Python Solution with Tests

> Tested Python solution for LeetCode 147 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 147, [Medium](/catalog/medium). Topics: [Linked List](/catalog/topics/linked-list), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/insertion-sort-list/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 147   # by problem number
lcpy gen -s insertion_sort_list   # by problem name
```

## Problem

Given the `head` of a singly linked list, sort the list using **insertion sort**, and return *the sorted list's head*.

The steps of the **insertion sort** algorithm:

1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
3. It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

![Insertion Sort Example](https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif)

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/03/04/sort1linked-list.jpg)

```
Input: head = [4,2,1,3]
Output: [1,2,3,4]
```

![Example 2](https://assets.leetcode.com/uploads/2021/03/04/sort2linked-list.jpg)

```
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
```

### Constraints

* The number of nodes in the list is in the range \[1, 5000]
* -5000 \<= Node.val \<= 5000

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/insertion_sort_list/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/insertion_sort_list/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from leetcode_py import ListNode


class Solution:
    # Time: O(n^2)
    # Space: O(1)
    def insertion_sort_list(self, head: ListNode[int] | None) -> ListNode[int] | None:
        dummy = ListNode[int](0)
        dummy.next = head
        current = head
        while current is not None and current.next is not None:
            next_node = current.next
            if current.val <= next_node.val:
                current = current.next
                continue
            current.next = next_node.next
            prev = dummy
            while prev.next is not None and prev.next.val < next_node.val:
                prev = prev.next
            next_node.next = prev.next
            prev.next = next_node
        return dummy.next
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.