LeetCode

2014.1.14 23:17

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

Solution:

　　The first thing I thought of about this problem is merge sort. It's weakness in space complexity is perfectly avoided with linked list, as you won't need another O(n) space when merging two sublists, and the process is completely sequential. These two properties make merge sort the perfect choice for this problem.

　　To put it simply, divide and conquer.

　　Time complexity is O(n * log(n)), space complexity is O(1).

Accepted code:

  1 // 1AC, incredibly smooth, keep it coming~
  2 /**
  3  * Definition for singly-linked list.
  4  * struct ListNode {
  5  *     int val;
  6  *     ListNode *next;
  7  *     ListNode(int x) : val(x), next(NULL) {}
  8  * };
  9  */
 10 class Solution {
 11 public:
 12     ListNode *sortList(ListNode *head) {
 13         // IMPORTANT: Please reset any member data you declared, as
 14         // the same Solution instance will be reused for each test case.
 15         if(head == nullptr || head->next == nullptr){
 16             return head;
 17         }
 18         
 19         int i, len;
 20         ListNode *ptr;
 21         
 22         ptr = head;
 23         len = 0;
 24         while(ptr != nullptr){
 25             ptr = ptr->next;
 26             ++len;
 27         }
 28         
 29         ListNode *h1, *h2;
 30         ptr = head;
 31         for(i = 0; i < len / 2 - 1; ++i){
 32             ptr = ptr->next;
 33         }
 34         h1 = head;
 35         h2 = ptr->next;
 36         ptr->next = nullptr;
 37         
 38         h1 = sortList(h1);
 39         h2 = sortList(h2);
 40         head = mergeList(h1, h2);
 41         
 42         return head;
 43     }
 44 private:
 45     ListNode *mergeList(ListNode *head1, ListNode *head2) {
 46         if(head1 == nullptr){
 47             return head2;
 48         }else if(head2 == nullptr){
 49             return head1;
 50         }
 51         
 52         ListNode *head = nullptr;
 53         ListNode *ptr = nullptr;
 54         
 55         while(head1 != nullptr && head2 != nullptr){
 56             if(head1->val < head2->val){
 57                 if(ptr == nullptr){
 58                     ptr = head1;
 59                     head1 = head1->next;
 60                     ptr->next = nullptr;
 61                     head = ptr;
 62                 }else{
 63                     ptr->next = head1;
 64                     head1 = head1->next;
 65                     ptr = ptr->next;
 66                     ptr->next = nullptr;
 67                 }
 68             }else{
 69                 if(ptr == nullptr){
 70                     ptr = head2;
 71                     head2 = head2->next;
 72                     ptr->next = nullptr;
 73                     head = ptr;
 74                 }else{
 75                     ptr->next = head2;
 76                     head2 = head2->next;
 77                     ptr = ptr->next;
 78                     ptr->next = nullptr;
 79                 }
 80             }
 81         }
 82         while(head1 != nullptr){
 83             if(ptr == nullptr){
 84                 ptr = head1;
 85                 head1 = head1->next;
 86                 ptr->next = nullptr;
 87                 head = ptr;
 88             }else{
 89                 ptr->next = head1;
 90                 head1 = head1->next;
 91                 ptr = ptr->next;
 92                 ptr->next = nullptr;
 93             }
 94         }
 95         while(head2 != nullptr){
 96             if(ptr == nullptr){
 97                 ptr = head2;
 98                 head2 = head2->next;
 99                 ptr->next = nullptr;
100                 head = ptr;
101             }else{
102                 ptr->next = head2;
103                 head2 = head2->next;
104                 ptr = ptr->next;
105                 ptr->next = nullptr;
106             }
107         }
108         
109         return head;
110     }
111 };