Sort List
MedPrompt
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:
- The number of nodes in the list is in the range
[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)?
Approaches
4 approaches with complexity analysis and trade-offs.
A simple but inefficient approach is to use a sorting algorithm with O(n^2) time complexity, like Selection Sort. We can iterate through the list, and for each node, find the node with the minimum value in the rest of the list and swap their values. This process is repeated for every node.
Algorithm
- Start with a pointer
currentat the head of the list. - While
currentis not null:- Create another pointer
runnerstarting fromcurrent.next. - Find the node with the minimum value in the sublist starting from
current. Let's call itminNode. - Swap the value of
currentwith the value ofminNode. - Move
currenttocurrent.next.
- Create another pointer
- Return the head of the list.
Walkthrough
This method iterates through the linked list, treating the current position as the position to place the next smallest element. For each position current, it scans the remainder of the list (runner) to find the node with the minimum value. Once found, the value of the current node is swapped with the value of the minimum node. This ensures that the prefix of the list up to current is sorted relative to the elements within that prefix. The outer loop moves current one step forward at a time, extending the sorted portion of the list until the entire list is sorted.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode sortList(ListNode head) { if (head == null) { return null; } ListNode current = head; while (current != null) { ListNode minNode = current; ListNode runner = current.next; while (runner != null) { if (runner.val < minNode.val) { minNode = runner; } runner = runner.next; } // Swap values int temp = current.val; current.val = minNode.val; minNode.val = temp; current = current.next; } return head; }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
In-place sorting with constant extra space.
Cons
Very slow for large lists and will likely result in a 'Time Limit Exceeded' error for the given constraints.
A straightforward approach is to leverage the efficiency of array-based sorting algorithms. We can traverse the linked list, store its values in an array, sort the array, and then iterate through the list again to update the node values from the sorted array.
Algorithm
- Handle the edge case where the list is empty or has one node.
- Create a dynamic array (like
ArrayListin Java). - Iterate through the linked list from head to tail, adding each node's value to the array.
- Sort the array using a built-in sorting function, which typically has a time complexity of O(n log n).
- Initialize a pointer
currentto the head of the list. - Iterate through the sorted array, updating the value of each node in the linked list with the corresponding element from the array.
- Return the original head of the list, which now contains sorted values.
Walkthrough
This method decouples the sorting logic from the linked list structure. First, the linked list is converted into a more sort-friendly data structure, an array. This takes O(n) time. Then, a standard, highly optimized sorting algorithm (like Timsort, used by Collections.sort in Java) is applied to the array, which takes O(n log n) time. Finally, the sorted values from the array are copied back into the original linked list nodes by traversing the list one more time. This final step also takes O(n) time. The overall time complexity is dominated by the sorting step.
import java.util.ArrayList;import java.util.Collections;import java.util.List; /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } List<Integer> values = new ArrayList<>(); ListNode current = head; while (current != null) { values.add(current.val); current = current.next; } Collections.sort(values); current = head; int i = 0; while (current != null) { current.val = values.get(i++); current = current.next; } return head; }}Complexity
Time
O(n log n)
Space
O(n)
Trade-offs
Pros
Relatively easy to implement.
Leverages highly optimized built-in sorting functions.
Cons
Requires O(n) extra space to store the list values, which does not meet the follow-up constraint of O(1) space.
Merge Sort is a divide-and-conquer algorithm that is well-suited for linked lists. This approach recursively splits the list into two halves, sorts them independently, and then merges the two sorted halves.
Algorithm
- Base Case: If the list is empty or has only one node, it's already sorted, so return it.
- Split: Find the middle of the linked list using the 'slow and fast pointer' technique. Split the list into two halves at the middle.
- Recurse: Recursively call the sort function on both halves.
- Merge: Merge the two sorted halves into a single sorted list and return its head.
Walkthrough
This approach implements the classic Merge Sort algorithm. The main function sortList first checks for the base case (a list of size 0 or 1). If not the base case, it finds the middle of the list using a helper function getMid. This function uses two pointers, slow and fast, where fast moves twice as fast as slow. When fast reaches the end, slow is at the middle. The list is then split into two sublists, left and right. The function then calls itself recursively on these two sublists. The returned sorted sublists are then merged by a merge helper function. The merge function takes two sorted lists and combines them into a single sorted list by iteratively picking the smaller of the two heads.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } // Step 1: Split the list into two halves ListNode mid = getMid(head); ListNode left = head; ListNode right = mid.next; mid.next = null; // Step 2: Sort each half left = sortList(left); right = sortList(right); // Step 3: Merge the sorted halves return merge(left, right); } private ListNode merge(ListNode list1, ListNode list2) { ListNode dummyHead = new ListNode(); ListNode tail = dummyHead; while (list1 != null && list2 != null) { if (list1.val < list2.val) { tail.next = list1; list1 = list1.next; } else { tail.next = list2; list2 = list2.next; } tail = tail.next; } tail.next = (list1 != null) ? list1 : list2; return dummyHead.next; } private ListNode getMid(ListNode head) { ListNode midPrev = null; ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { midPrev = slow; slow = slow.next; fast = fast.next.next; } return midPrev; }}Complexity
Time
O(n log n)
Space
O(log n)
Trade-offs
Pros
Achieves the optimal O(n log n) time complexity.
Conceptually elegant and a classic divide-and-conquer example.
Cons
The recursion stack uses O(log n) space, which does not satisfy the O(1) space follow-up constraint.
This is the most optimal approach, satisfying both the O(n log n) time and O(1) space constraints. It's an iterative version of Merge Sort. Instead of recursively splitting the list from the top down, it starts by merging small sublists of size 1 and iteratively merges them into larger sorted sublists until the entire list is sorted.
Algorithm
- First, calculate the length
nof the linked list. - Create a
dummynode and point itsnextto thehead. - Start an outer loop for the sublist size
size, from 1 ton, doubling it in each iteration (size = 1, 2, 4, ...). - Inside, run an inner loop to iterate through the list, merging pairs of sublists of the current
size.- For each pair, split the list into
left(of sizesize) andright(of sizesize). - Merge the
leftandrightsublists. - Connect the merged sublist back into the main list.
- For each pair, split the list into
- After the loops finish,
dummy.nextwill point to the head of the fully sorted list.
Walkthrough
This bottom-up approach avoids recursion and its associated space overhead. It works by making multiple passes over the list. In the first pass, it merges sublists of size 1 to produce sorted sublists of size 2. In the second pass, it merges sorted sublists of size 2 to produce sorted sublists of size 4, and so on. This continues until the sublist size is greater than or equal to the list's length.
A dummy node is used to simplify handling the head of the list. In each pass (controlled by size), we iterate through the list, splitting it into a left part and a right part, each of at most size nodes. These two parts are then merged, and the resulting sorted list is appended to the tail of the list sorted so far. This process is repeated until all nodes for the current pass are merged.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } int n = 0; ListNode curr = head; while (curr != null) { n++; curr = curr.next; } ListNode dummy = new ListNode(0, head); for (int size = 1; size < n; size <<= 1) { ListNode tail = dummy; curr = dummy.next; while (curr != null) { ListNode left = curr; ListNode right = split(left, size); curr = split(right, size); tail.next = merge(left, right); while (tail.next != null) { tail = tail.next; } } } return dummy.next; } private ListNode split(ListNode head, int size) { if (head == null) return null; for (int i = 1; i < size && head.next != null; i++) { head = head.next; } ListNode secondHead = head.next; head.next = null; return secondHead; } private ListNode merge(ListNode list1, ListNode list2) { ListNode dummyHead = new ListNode(); ListNode tail = dummyHead; while (list1 != null && list2 != null) { if (list1.val < list2.val) { tail.next = list1; list1 = list1.next; } else { tail.next = list2; list2 = list2.next; } tail = tail.next; } tail.next = (list1 != null) ? list1 : list2; return dummyHead.next; }}Complexity
Time
O(n log n)
Space
O(1)
Trade-offs
Pros
Most efficient solution.
Meets the time (O(n log n)) and space (O(1)) complexity requirements of the follow-up question.
Cons
Significantly more complex to understand and implement correctly compared to the recursive version.
Solutions
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public 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 t = slow . next ; slow . next = null ; ListNode l1 = SortList ( head ); ListNode l2 = SortList ( t ); ListNode dummy = new ListNode (); ListNode cur = dummy ; while ( l1 != null && l2 != null ) { if ( l1 . val <= l2 . val ) { cur . next = l1 ; l1 = l1 . next ; } else { cur . next = l2 ; l2 = l2 . next ; } cur = cur . next ; } cur . next = l1 == null ? l2 : l1 ; return dummy . next ; } }/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ 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 t = slow . next ; slow . next = null ; ListNode l1 = sortList ( head ); ListNode l2 = sortList ( t ); ListNode dummy = new ListNode (); ListNode cur = dummy ; while ( l1 != null && l2 != null ) { if ( l1 . val <= l2 . val ) { cur . next = l1 ; l1 = l1 . next ; } else { cur . next = l2 ; l2 = l2 . next ; } cur = cur . next ; } cur . next = l1 == null ? l2 : l1 ; return dummy . next ; } }/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var sortList = function (head) { if (!head || !head.next) { return head; } let slow = head; let fast = head.next; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } let t = slow.next; slow.next = null; let l1 = sortList(head); let l2 = sortList(t); const dummy = new ListNode(); let cur = dummy; while (l1 && l2) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 || l2; return dummy.next; };/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * sortList ( ListNode * head ) { if ( ! head || ! head -> next ) return head ; auto * slow = head ; auto * fast = head -> next ; while ( fast && fast -> next ) { slow = slow -> next ; fast = fast -> next -> next ; } auto * t = slow -> next ; slow -> next = nullptr ; auto * l1 = sortList ( head ); auto * l2 = sortList ( t ); auto * dummy = new ListNode (); auto * cur = dummy ; while ( l1 && l2 ) { if ( l1 -> val <= l2 -> val ) { cur -> next = l1 ; l1 = l1 -> next ; } else { cur -> next = l2 ; l2 = l2 -> next ; } cur = cur -> next ; } cur -> next = l1 ? l1 : l2 ; return dummy -> next ; } };# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def sortList ( self , head : ListNode ) -> ListNode : if head is None or head . next is None : return head slow , fast = head , head . next while fast and fast . next : slow , fast = slow . next , fast . next . next t = slow . next slow . next = None l1 , l2 = self . sortList ( head ), self . sortList ( t ) dummy = ListNode () cur = dummy while l1 and l2 : if l1 . val <= l2 . val : cur . next = l1 l1 = l1 . next else : cur . next = l2 l2 = l2 . next cur = cur . next cur . next = l1 or l2 # add the rest return dummy . nextVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.