Log inSign up
mediumLeetCodeNot Started

Sort List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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

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

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]
Explanation: List is sorted in ascending numerical order.

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Explanation: List sorted in ascending order.

Example 3:

Input: head = []
Output: []
Explanation: Empty list produces empty list.

Constraints:

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

1. Array Value Extraction & Built-In Sorting

Intuition

1. Collect all node values into a vector/list vals. 2. Sort vals in ascending order. 3. Traverse the linked list and overwrite each node.val with the sorted value.

When to apply: Quick, practical solution when extra O(N) space is permitted and node references need not remain intact.

Algorithm

  1. Traverse linked list and append values into array.
  2. Sort array using built-in dual-pivot Quicksort / Timsort.
  3. Traverse list again and overwrite values sequentially.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode() : val(0), next(nullptr) {}
9 ListNode(int x) : val(x), next(nullptr) {}
10 ListNode(int x, ListNode *next) : val(x), next(next) {}
11};
12
13class Solution {
14public:
15 ListNode* sortList(ListNode* head) {
16 if (!head || !head->next) return head;
17
18 std::vector<int> vals;
19 ListNode* curr = head;
20 while (curr != nullptr) {
21 vals.push_back(curr->val);
22 curr = curr->next;
23 }
24
25 std::sort(vals.begin(), vals.end());
26
27 curr = head;
28 for (int v : vals) {
29 curr->val = v;
30 curr = curr->next;
31 }
32 return head;
33 }
34};
35
36int main() {
37 ListNode* head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
38 Solution sol;
39 ListNode* res = sol.sortList(head);
40 while (res != nullptr) {
41 std::cout << res->val << " ";
42 res = res->next;
43 }
44 std::cout << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N log N) — Extracting values is O(N), sorting is O(N log N), and rewriting is O(N). Total time is O(N log N).
  • Space complexity: O(N) — Allocates an auxiliary array holding all N values: O(N) space.

2. Top-Down Recursive Merge Sort

Intuition

1. Base case: If head == null || head.next == null, return head. 2. Find middle node using slow and fast pointers. Maintain prev so that prev.next = null effectively splits the list into two disconnected halves. 3. left = sortList(head), right = sortList(mid). 4. Return merge(left, right).

When to apply: The most widely implemented and intuitive O(N log N) sorting pattern for linked lists.

Algorithm

  1. Base case: return if head is null or single node.
  2. Split list into two halves using Fast and Slow pointers.
  3. Sever connection between halves.
  4. Recursively sort left and right halves.
  5. Merge two sorted halves and return new head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12private:
13 ListNode* merge(ListNode* l1, ListNode* l2) {
14 ListNode dummy(0);
15 ListNode* tail = &dummy;
16
17 while (l1 != nullptr && l2 != nullptr) {
18 if (l1->val <= l2->val) {
19 tail->next = l1;
20 l1 = l1->next;
21 } else {
22 tail->next = l2;
23 l2 = l2->next;
24 }
25 tail = tail->next;
26 }
27 tail->next = (l1 != nullptr) ? l1 : l2;
28 return dummy.next;
29 }
30
31public:
32 ListNode* sortList(ListNode* head) {
33 if (!head || !head->next) return head;
34
35 ListNode* prev = nullptr;
36 ListNode* slow = head;
37 ListNode* fast = head;
38
39 while (fast != nullptr && fast->next != nullptr) {
40 prev = slow;
41 slow = slow->next;
42 fast = fast->next->next;
43 }
44
45 prev->next = nullptr; // Split into two halves
46
47 ListNode* l1 = sortList(head);
48 ListNode* l2 = sortList(slow);
49
50 return merge(l1, l2);
51 }
52};
53
54int main() {
55 ListNode* head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
56 Solution sol;
57 ListNode* res = sol.sortList(head);
58 while (res != nullptr) {
59 std::cout << res->val << " ";
60 res = res->next;
61 }
62 std::cout << std::endl;
63 return 0;
64}

Time & Space Complexity

  • Time complexity: O(N log N) — The recursion tree has depth log N, and at each level N comparisons are made during merging: O(N log N) total time.
  • Space complexity: O(log N) call stack — The recursive call stack consumes O(log N) frames.

3. Bottom-Up Iterative Merge Sort

Intuition

1. Compute total length N of the list. 2. Use a sentinel dummy with dummy.next = head. 3. For step = 1, 2, 4, ... < N: - Set prev = dummy, curr = dummy.next. - While curr != null: a. Split off left = curr of size step. b. Split off right of size step. c. Save nextSublist = remaining. d. Merge left and right and attach to prev.next. e. Advance prev to the end of merged sublist and curr = nextSublist. 4. Return dummy.next.

When to apply: The follow-up requirement demanding strict O(1) auxiliary memory without any recursive call-stack overhead.

Algorithm

  1. Find total list length N.
  2. Loop with step size doubling each pass: 1, 2, 4, 8, ...
  3. Split adjacent sublists of size step.
  4. Merge them in-place and reconnect into main chain.
  5. Repeat until step size >= N.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Left sublist starts at node 4; right sublist starts at node 1
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Left sublist starts at node 4; right sublist starts at node 1.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12private:
13 ListNode* split(ListNode* head, int step) {
14 if (!head) return nullptr;
15 for (int i = 1; head->next && i < step; ++i) {
16 head = head->next;
17 }
18 ListNode* rest = head->next;
19 head->next = nullptr;
20 return rest;
21 }
22
23 std::pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) {
24 ListNode dummy(0);
25 ListNode* tail = &dummy;
26 while (l1 && l2) {
27 if (l1->val <= l2->val) {
28 tail->next = l1;
29 l1 = l1->next;
30 } else {
31 tail->next = l2;
32 l2 = l2->next;
33 }
34 tail = tail->next;
35 }
36 tail->next = (l1) ? l1 : l2;
37 while (tail->next) tail = tail->next;
38 return {dummy.next, tail};
39 }
40
41public:
42 ListNode* sortList(ListNode* head) {
43 if (!head || !head->next) return head;
44
45 int length = 0;
46 ListNode* curr = head;
47 while (curr) {
48 length++;
49 curr = curr->next;
50 }
51
52 ListNode dummy(0, head);
53
54 for (int step = 1; step < length; step <<= 1) {
55 ListNode* prev = &dummy;
56 curr = dummy.next;
57
58 while (curr) {
59 ListNode* left = curr;
60 ListNode* right = split(left, step);
61 curr = split(right, step);
62
63 auto [mergedHead, mergedTail] = merge(left, right);
64 prev->next = mergedHead;
65 prev = mergedTail;
66 }
67 }
68
69 return dummy.next;
70 }
71};
72
73int main() {
74 ListNode* head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
75 Solution sol;
76 ListNode* res = sol.sortList(head);
77 while (res != nullptr) {
78 std::cout << res->val << " ";
79 res = res->next;
80 }
81 std::cout << std::endl;
82 return 0;
83}

Time & Space Complexity

  • Time complexity: O(N log N) — There are log2(N) passes over the list, each pass taking O(N) operations: O(N log N) total time.
  • Space complexity: O(1) auxiliary — All sublist splits and merges are performed iteratively with pointers: strict O(1) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Array Value Extraction & Built-In SortingO(N log N)O(N)Extract all node values into an array, sort the array using standard sorting algorithms (O(N log N)), and rewrite values into the linked list.High time complexity
2.Top-Down Recursive Merge SortO(N log N)O(log N) call stackRecursively split the linked list in half using Fast & Slow pointers, sort each half recursively, and merge them with a dummy pointer in O(1) auxiliary space.—
3.Bottom-Up Iterative Merge SortOptimalO(N log N)O(1) auxiliaryIteratively merge adjacent sublists of size step = 1, 2, 4, 8, ... in bottom-up fashion, achieving strict O(N log N) time and O(1) auxiliary space.—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not breaking the link (prev.next = null) during top-down split, resulting in infinite recursion or cyclic lists.

Pitfall 2:

Attempting Quicksort on singly linked lists: poor pivot choice and lack of backward pointers make standard Quicksort degrade to O(N2) or require O(N) auxiliary space.

Pitfall 3:

Losing mergedTail in bottom-up merge, causing detached sublist chains.

Back to DSA Sheet