Given the head of a linked list, return the list sorted in ascending order.
The solution must run in O(n log n) time and use only O(1) extra space (constant space, ignoring call stack).
Input: head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]
Input: head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]
Input: head = []
Output: []
Merge sort is the ideal algorithm for linked lists as it does not require random access and achieves O(n log n) time.
The approach is:
- Divide: Find the middle of the list using the slow/fast pointer technique and split the list into two halves.
- Conquer: Recursively sort each half.
- Combine: Merge the two sorted halves using the standard sorted merge operation.
- Base case: a list of 0 or 1 nodes is already sorted.
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class SortList {
public ListNode sortList(ListNode head) {
// Base case: 0 or 1 nodes
if (head == null || head.next == null) return head;
// Step 1: Find middle and split
ListNode mid = getMid(head);
ListNode right = mid.next;
mid.next = null; // disconnect left and right halves
// Step 2: Recursively sort both halves
ListNode leftSorted = sortList(head);
ListNode rightSorted = sortList(right);
// Step 3: Merge the sorted halves
return merge(leftSorted, rightSorted);
}
private ListNode getMid(ListNode head) {
ListNode slow = head;
ListNode fast = head.next; // using head.next so slow stops at first middle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
Complexity Analysis:
Time complexity: O(n log n) — the list is divided in half log n times and each merge step takes O(n) total.
Space complexity: O(log n) for the recursion call stack. An iterative bottom-up merge sort achieves true O(1) space.