Sort a singly linked list in ascending order, ideally with linked-list merge sort. Test your code and explore the solution. Free online practice.

Sort List

Binary Tree Inorder Traversal

Combination Sum III

Sort a singly linked list in ascending order, ideally with linked-list merge sort.

Given the `head` of a singly linked list, return the head of the list sorted in ascending order. The input is a real `ListNode` chain built by the judge from a flat JSON array such as `[4, 2, 1, 3]`, and whatever linked list you return is serialized back to the same flat-array form for grading.

You may solve this by collecting values into an array and rebuilding the list, but interviewers usually want the linked-list merge-sort solution because it keeps the sorting work on the nodes themselves.

**Input / output**
- Input: `head: ListNode`
- Output: `ListNode` — the head of the sorted linked list

**Examples**
1. `head = [4, 2, 1, 3]` returns `[1, 2, 3, 4]`.
2. `head = [-1, 5, 3, 4, 0]` returns `[-1, 0, 3, 4, 5]`.
3. `head = []` returns `[]`.

**Constraints**
- `0 <= number of nodes <= 50,000`
- `-100,000 <= node value <= 100,000`
- The list may contain duplicate values.

**Follow-up**
Can you sort the list in `O(n log n)` time without converting it to an array first, and explain why merge sort is a natural fit for linked lists?

A straightforward approach is to walk the linked list once, copy every value into an array, sort that array, and then build a new sorted linked list from those values. This is easy to reason about and still runs in `O(n log n)` time, but it uses `O(n)` extra space for the copied values and rebuilt nodes.

Warm up by collecting values, sorting them, and rebuilding the list

The optimal linked-list solution uses top-down merge sort. Split the list into two halves with slow and fast pointers, recursively sort each half, then merge the two sorted linked lists. Every level touches each node once, so the time complexity is `O(n log n)`, and the extra space is `O(log n)` from the recursion stack.