Sort [4,2,1,3]
Input
[4, 2, 1, 3]
Output
[1, 2, 3, 4]
The list is sorted in ascending order.
Full lesson preview
Sort a linked list using merge sort
Sort a singly linked list with merge sort. Input is a Python list of node values.
Python practice30 minLinked ListsAdvancedLast updated March 27, 2026
Problem statement
Given the head of a singly linked list (represented as a Python list), sort the list in ascending order using merge sort on the linked list and return the sorted values as a Python list.
You should implement the linked-list variant of merge sort (split by finding the midpoint, recursively sort halves, merge). This avoids extra O(n log n) array copies and demonstrates pointer-based sorting.
Task
Implement merge sort on a linked list representation and return the sorted values.
Examples
Input format
A Python list of integers representing the linked list node values.
Output format
A Python list of integers representing the sorted linked list values.
Constraints
- 0 <= len(list) <= 10^4 for tests
- Values are integers and may include negatives and duplicates
Aim for O(n log n) time and O(log n) recursion stack space.
Samples
Sample 1
Input
[-1, 5, 3, 4, 0]
Output
[-1, 0, 3, 4, 5]
Sorted ascending.