> ## 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.

# Sort List Python Solution with Tests

> Tested Python solution for LeetCode 148 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 148, Medium. Topics: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort. [View on LeetCode](https://leetcode.com/problems/sort-list/description/).

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

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

## Problem

Given the `head` of a linked list, return *the list after sorting it in ascending order*.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg)

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

![Example 2](https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg)

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

```
Input: head = []
Output: []
```

### Constraints

* The number of nodes in the list is in the range \[0, 5 \* 10^4].
* -10^5 \<= Node.val \<= 10^5

**Follow up:** Can you sort the linked list in `O(n logn)` time and `O(1)` memory (i.e. constant space)?

## Solution

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

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


class Solution:
    # Time: O(n log n) — bottom-up merge sort, log n passes each O(n)
    # Space: O(1) — iterative, pointers only
    def sort_list(self, head: ListNode[int] | None) -> ListNode[int] | None:
        if not head or not head.next:
            return head

        # Find length
        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        dummy: ListNode[int] = ListNode[int](0)
        dummy.next = head
        size = 1
        while size < length:
            curr = dummy.next
            tail = dummy
            while curr:
                left = curr
                right = self._split(left, size)
                curr = self._split(right, size) if right else None
                tail = self._merge(left, right, tail)
            size *= 2
        return dummy.next

    @staticmethod
    def _split(head: ListNode[int] | None, size: int) -> ListNode[int] | None:
        """Cut after `size` nodes; return the head of the second half."""
        for _ in range(size - 1):
            if head is None or head.next is None:
                break
            head = head.next
        if head is None:
            return None
        nxt = head.next
        head.next = None
        return nxt

    @staticmethod
    def _merge(
        left: ListNode[int] | None, right: ListNode[int] | None, tail: ListNode[int]
    ) -> ListNode[int]:
        """Merge two sorted lists onto tail; return the new tail."""
        while left and right:
            if left.val <= right.val:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next
        tail.next = left if left else right
        while tail.next:
            assert tail.next is not None
            tail = tail.next
        return tail
```

## Complexity

| Time                                                      | Space                           |
| --------------------------------------------------------- | ------------------------------- |
| O(n log n) — bottom-up merge sort, log n passes each O(n) | O(1) — iterative, pointers only |

## Tags

[Grind](/catalog/grind), [NeetCode All](/catalog/neetcode).