Given the head of a linked list, return the list after sorting it in ascending order.
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]
Example 3:
Input: head = [] Output: []
Constraints:
[0, 5 * 104].-105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Problem Overview: Given the head of a singly linked list, you need to sort the nodes in ascending order and return the sorted list. The constraint that makes this problem interesting is achieving O(n log n) time while working directly with a linked list structure.
Approach 1: Convert to Array and Sort (O(n log n) time, O(n) space)
The simplest idea is to copy all node values into an array, use a built-in sorting algorithm, then rebuild the linked list in sorted order. Sorting an array costs O(n log n), and reconstructing the list takes O(n). The drawback is extra memory usage because all elements are stored in an auxiliary array, making space complexity O(n). This approach works in practice but ignores the structure of the linked list and is usually not the expected interview solution.
Approach 2: Merge Sort on Linked List (Top-Down) (O(n log n) time, O(log n) space)
The classic solution applies divide and conquer with merge sort. First, split the list into two halves using the slow and fast pointer technique from the two pointers pattern. Recursively sort both halves, then merge the two sorted lists. The merge step walks through both lists and connects the smaller node each time. Because each level of recursion processes all nodes once and there are log n levels, the total time complexity is O(n log n). The recursion stack introduces O(log n) space overhead.
Approach 3: Bottom-Up Merge Sort for Linked List (O(n log n) time, O(1) space)
The iterative bottom-up merge sort eliminates recursion and achieves constant extra space. Start by merging sublists of size 1, then size 2, 4, 8, and so on until the entire list is sorted. For each pass, iterate through the list, split it into pairs of segments of the current size, and merge them using a standard linked-list merge routine. Because nodes are rearranged using pointer manipulation rather than extra storage, the algorithm maintains O(1) auxiliary space. The list is still processed log n times, giving overall O(n log n) time complexity.
Recommended for interviews: Top-down merge sort is the most common interview solution because it is easier to implement and clearly demonstrates understanding of linked list splitting and merging. Bottom-up merge sort is more advanced and shows strong mastery of pointer manipulation and space optimization. Interviewers typically expect at least the recursive merge sort approach with correct O(n log n) complexity.
This approach leverages the merge sort algorithm, which is well-suited for linked lists compared to arrays. The merge sort algorithm uses a divide-and-conquer strategy: it splits the list in half recursively until it can no longer be divided, and then merges the sublists back together in sorted order.
The C implementation uses two primary functions: sortList for recursively dividing and sorting the list, and merge for merging two sorted lists. The function splits the list using a slow-fast pointer method to find the midpoint, then recursively sorts each half, and finally merges the sorted halves. The dummy node is utilized to simplify merging logic.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), where n is the number of nodes in the list. Space Complexity: O(log n) due to recursive stack space.
This approach implements an iterative, bottom-up merge sort, avoiding the recursion and thus achieving O(1) space complexity beyond the input and output list. The list isn't split recursively but is treated progressively as sublists of increasing sizes are sorted and merged.
This C implementation of the bottom-up merge sort iteratively increases the block size for merging. It calculates the size n of the list first. Using a dummy node, it repeatedly splits the list into sublists of increasing size and merges them until the entire list is sorted.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) where n is the number of nodes. Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Merge Sort on Linked List | Time Complexity: O(n log n), where n is the number of nodes in the list. Space Complexity: O(log n) due to recursive stack space. |
| Bottom-Up Merge Sort for Linked List | Time Complexity: O(n log n) where n is the number of nodes. Space Complexity: O(1). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert to Array and Sort | O(n log n) | O(n) | Quick implementation when extra memory is acceptable |
| Merge Sort on Linked List (Top-Down) | O(n log n) | O(log n) | Standard interview solution using recursion and slow/fast pointer splitting |
| Bottom-Up Merge Sort for Linked List | O(n log n) | O(1) | When constant extra space is required and iterative pointer manipulation is preferred |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 views views
Watch 9 more video solutions →Practice Sort List with our built-in code editor and test cases.
Practice on FleetCode