Sort List
Sort List is a medium linked list problem solved with the miscellaneous pattern.
The best approach, optimal (top-down merge sort), runs in O(n log n) time and O(log n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from copy, sort, write back up.
Problem
Sort a linked list in ascending order and return its head.
Examples
Example 1
- Input
head = [4, 2, 1, 3]- Output
[1, 2, 3, 4]
Example 2
- Input
head = [-1, 5, 3, 4, 0]- Output
[-1, 0, 3, 4, 5]
Constraints
- The list has
0to5 * 10^4nodes. - Follow-up: O(n log n) time and O(1) memory.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Copy, sort, write back | O(n log n) | O(n) |
| Optimal (top-down merge sort) | O(n log n) | O(log n) |
1Copy, sort, write back
O(n log n)O(n)Copy the values into an array, sort it and write the values back into the nodes.
- Collect values, Collections.sort, overwrite node values.
class Solution {
public ListNode sortList(ListNode head) {
List<Integer> v = new ArrayList<>();
for (ListNode p = head; p != null; p = p.next) v.add(p.val);
Collections.sort(v);
ListNode p = head;
for (int x : v) { p.val = x; p = p.next; }
return head;
}
}class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
v = []
p = head
while p is not None:
v.append(p.val)
p = p.next
v.sort()
p = head
for x in v:
p.val = x
p = p.next
return headclass Solution {
public:
ListNode* sortList(ListNode* head) {
vector<int> v;
for (ListNode* p = head; p != nullptr; p = p->next) v.push_back(p->val);
sort(v.begin(), v.end());
ListNode* p = head;
for (int x : v) { p->val = x; p = p->next; }
return head;
}
};function sortList(head) {
const v = [];
for (let p = head; p !== null; p = p.next) v.push(p.val);
v.sort((a, b) => a - b);
let p = head;
for (const x of v) { p.val = x; p = p.next; }
return head;
}2Optimal (top-down merge sort)
O(n log n)O(log n)Recursion stack. A bottom-up merge sort gets this down to O(1).Split the list at its middle (stop slow one node before the middle so you can cut), sort both halves recursively and merge them with a dummy node.
- If the list has 0 or 1 nodes, return it.
- slow = head, fast = head.next; advance to find the end of the first half; cut.
- Return merge(sort(left), sort(right)).
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode right = slow.next;
slow.next = null;
return merge(sortList(head), sortList(right));
}
private ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(), t = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { t.next = a; a = a.next; }
else { t.next = b; b = b.next; }
t = t.next;
}
t.next = a != null ? a : b;
return dummy.next;
}
}class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
slow, fast = head, head.next
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
right = slow.next
slow.next = None
return self.merge(self.sortList(head), self.sortList(right))
def merge(self, a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
t = dummy
while a is not None and b is not None:
if a.val <= b.val:
t.next = a
a = a.next
else:
t.next = b
b = b.next
t = t.next
t.next = a if a is not None else b
return dummy.nextclass Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* right = slow->next;
slow->next = nullptr;
return merge(sortList(head), sortList(right));
}
private:
ListNode* merge(ListNode* a, ListNode* b) {
ListNode dummy;
ListNode* t = &dummy;
while (a != nullptr && b != nullptr) {
if (a->val <= b->val) { t->next = a; a = a->next; }
else { t->next = b; b = b->next; }
t = t->next;
}
t->next = a != nullptr ? a : b;
return dummy.next;
}
};function sortList(head) {
if (head === null || head.next === null) return head;
let slow = head, fast = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
const right = slow.next;
slow.next = null;
return merge(sortList(head), sortList(right));
}
function merge(a, b) {
const dummy = new ListNode();
let t = dummy;
while (a !== null && b !== null) {
if (a.val <= b.val) { t.next = a; a = a.next; }
else { t.next = b; b = b.next; }
t = t.next;
}
t.next = a !== null ? a : b;
return dummy.next;
}Edge cases to test
- Empty list or one node
- Already sorted input
Hints
Hint 1
Merge sort fits linked lists: splitting uses slow/fast pointers and merging needs no extra array.
FAQ
What is the best time complexity for Sort List?
Optimal (top-down merge sort) runs in O(n log n) time and O(log n) extra space.
Which pattern does Sort List use?
It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Copy List with Random Pointer, Intersection of Two Linked Lists.
Is there a brute force solution for Sort List?
Yes. Copy, sort, write back takes O(n log n) time and O(n) space. Copy the values into an array, sort it and write the values back into the nodes.
Which edge cases should I test for Sort List?
Empty list or one node; Already sorted input.