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 <= 105Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
The key challenge in #148 Sort List is to sort a singly linked list in O(n log n) time while keeping space usage minimal. Since linked lists do not support random access, traditional array-based sorting techniques are less efficient. A common strategy is to apply Merge Sort, which naturally fits the linked list structure.
The idea is to use the two-pointer technique (slow and fast pointers) to find the middle of the list and split it into two halves. Each half is then recursively sorted using the same approach. Finally, the two sorted halves are merged together using a standard linked-list merge process.
This divide-and-conquer strategy ensures optimal performance with O(n log n) time complexity. The merging process works efficiently because nodes can be rearranged by adjusting pointers rather than copying values. This approach is widely preferred in coding interviews due to its efficiency and clean logic.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Merge Sort on Linked List | O(n log n) | O(log n) (recursion stack) |
| Convert to Array + Sort | O(n log n) | O(n) |
NeetCode
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.
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.
1struct ListNode* sortList(struct ListNode* head) {
2 // base case
3 if (!head || !head->next) return head;
4
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.
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.
Time Complexity: O(n log n) where n is the number of nodes. Space Complexity: O(1).
1var sortList
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, one approach is to copy all node values into an array, sort the array, and then rebuild the list. While simple, it uses extra O(n) space and is generally not the most optimal interview solution.
Yes, variations of sorting linked lists and implementing merge sort on linked lists frequently appear in FAANG-style interviews. The problem tests understanding of linked list manipulation, divide-and-conquer techniques, and pointer management.
The optimal approach is merge sort applied directly to the linked list. It divides the list using slow and fast pointers, recursively sorts the halves, and merges them. This achieves O(n log n) time complexity while maintaining efficient pointer manipulation.
Merge sort works well with linked lists because it does not require random access. Splitting and merging lists can be done by simply adjusting pointers, making it more efficient than algorithms like quicksort or heapsort in this structure.
The JavaScript implementation uses a bottom-up, iterative merge sort technique. After calculating the list length, it applies split and merge operations in increasing steps sizes to order the list.