Sponsored
Sponsored
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
5 // split list into halves
6 struct ListNode *slow = head, *fast = head->next;
7 while (fast && fast->next) {
8 slow = slow->next;
9 fast = fast->next->next;
10 }
11 struct ListNode* mid = slow->next;
12 slow->next = NULL;
13
14 // recursively sort the sublists
15 struct ListNode* left = sortList(head);
16 struct ListNode* right = sortList(mid);
17
18 // merge both halves
19 return merge(left, right);
20}
21
22struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
23 struct ListNode dummy;
24 struct ListNode* tail = &dummy;
25 while (l1 && l2) {
26 if (l1->val < l2->val) {
27 tail->next = l1;
28 l1 = l1->next;
29 } else {
30 tail->next = l2;
31 l2 = l2->next;
32 }
33 tail = tail->next;
34 }
35 tail->next = l1 ? l1 : l2;
36 return dummy.next;
37}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).
1struct ListNode
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.