Description
Sort a linked list in time using constant space complexity.
Analysis
It is better to solve this problem with MergeSort than QuickSort, as we do not enjoy random access in a linked list. The easiest way to implement MergeSort is to do it recursively. Though the stack space used by recursion is , which slightly violates the constant space requirement, I do not bother to do a loop-version MergeSort here.
One trick of implementing MergeSort is how we identify the pointer. The naivest way is to iterate through the list to find the pointer between during each recursion. Though the time complexity is still , but it suffers from a larger constant. A better way to do it is to utilize the fact that we visit each node in the list following the exactly the same order of the nodes in the list. Thus we make a “global” pointer indicating which node we are currently at, after visiting which we move to . In this case, after we are finished with the left part , the pointer will naturally be at .
Solution
1 // Merge Sort for linked list
2 class Solution {
3 public:
4 ListNode *sortList(ListNode *head) {
5 int num_node = 0;
6 ListNode * pt = head;
7 while(pt){
8 pt = pt->next;
9 num_node ++;
10 }
11 head = mergeSort(head, num_node);
12 return head;
13 }
14 ListNode * mergeSort(ListNode*& head, int num_node){
15 if (num_node == 0)
16 return nullptr;
17 if (num_node == 1){
18 ListNode * head_cache = head;
19 head = head->next; // key: head is advanced to the next element
20 head_cache->next = nullptr; // do not forget this line
21 return head_cache;
22 }
23 int num_left = num_node >> 1, num_right = num_node - num_left;
24 ListNode * left_head = mergeSort(head, num_left);
25 ListNode * right_head =mergeSort(head, num_right);
26 return merge(left_head, right_head);
27 }
28 ListNode * merge(ListNode * left, ListNode * right){
29 ListNode new_head(-1);
30 ListNode *pt= &new_head;
31 while(left && right){
32 if (left->val < right->val){
33 pt->next = left;
34 left = left->next;
35 }
36 else{
37 pt->next = right;
38 right = right->next;
39 }
40 pt = pt->next;
41 }
42 ListNode * non_emp_ptr = (left)?left:right;
43 while(non_emp_ptr){
44 pt->next = non_emp_ptr;
45 non_emp_ptr = non_emp_ptr->next;
46 pt=pt->next;
47 }
48 pt->next = nullptr;
49 return new_head.next;
50 }
51 };