Leetcode: Sort List

Problem:

Sort a linked list in O(n log n) time using constant space complexity.

Hide Tags

 Linked List Sort

Show Similar Problems

--------------------------------------------

1. O(nlogn) sort:  only merge sort, heap sort and quick sort can achieve this goal. But all of them are using recursion, and therefore they are using non-constant space. So we need to do some modifications on them, e.g., we can use iteration to take place the recursion. 

For quick sort, the iteration doesn't work. But for merge sort, it's possible to use recursion. the general idea can be seen below:

we can do recursion one by one in each interval loop. 

In the original merge sort algorithm, when merge two halves into one, we need to create the third vector to temporally store the merged values. This will introduce extra space usage and not constant space. Here we using a method to do merging two halves into one without introducing an additional space: 

here we use an example when interval=2:

/////////////////////////////////////////////////////

//codes

class Solution {

public:

       ListNode* sortList(ListNode* head) {

              //check input

              if (head == NULL || head->next == NULL)return head;

              //dummy node

              ListNode *dum = new ListNode(-1);

              dum->next = head;

              ListNode *upHead = dum, *downHead = dum;

              ListNode *tmp = NULL;

              //get the number of nodes

              int len = 0;

              while (head != NULL){

                     len++;

                     head = head->next;

              }

              //outter loop for sort with diff. intervals

              for (int interval = 1; interval < len; interval = interval * 2){

                     //clear pointers

                     upHead = dum;

                     downHead = dum;

                     //locate the downHead for the first run

                     for (int j = 0; j < interval; j++){

                           downHead = downHead->next;

                     }

                     //check loop stop condition

                     if (downHead->next == NULL)break;

                     //inner loop

                     for (int i = 1;; i++){

                           //check loop stop condition

                           if (downHead->next == NULL)break;

                           int countDownHead = 0;

                           //sort the two half lists

                           while (countDownHead<interval){

                                  //check loop stop condition

                                  if (downHead->next == NULL || upHead == downHead)break;

                                  if (upHead->next->val>downHead->next->val){

                                         tmp = upHead->next;

                                         upHead->next = downHead->next;

                                         downHead->next = downHead->next->next;

                                         upHead->next->next = tmp;

                                         //update upNode

                                         upHead = upHead->next;

                                         countDownHead++;//count downHead was moved for how many times

                                  }

                                  else{

                                         upHead = upHead->next;

                                         //if (upHead == downHead)break;

                                  }

                           }

                           //locate the downHead to the end of previous run

                           for (int j = 0; j < interval - countDownHead; j++){

                                  if (downHead == NULL || downHead->next == NULL)break;

                                  downHead = downHead->next;

                           }

                           upHead = downHead;

                           //locate the downHead to the begin of next run

                           for (int j = 0; j < interval; j++){

                                  if (downHead == NULL || downHead->next == NULL)break;

                                  downHead = downHead->next;

                           }

                     }

              }

              head = dum->next;

              delete dum;

              return head;

       }

};