1 void mergeList(ListNode *a, ListNode *b, ListNode *&h, ListNode *&t) { 2   h = t = NULL; 3   while (a && b) { 4     ListNode *c = NULL; 5     if (a->val <= b->val) { 6       c = a; 7       a = a->next; 8     } 9     else {10       c = b;11       b = b->next;12     }13     if (!h)14       h = t = c;15     else {16       t->next = c;17       t = t->next;18     }19   }20   while (a) {21     t->next = a;22     t = t->next;23     a = a->next;24   }25   while (b) {26     t->next = b;27     t = t->next;28     b = b->next;29   }30 }31     32 ListNode *sortList(ListNode *head) {33   ListNode *prev = NULL;34   ListNode *h1 = NULL;35   ListNode *h2 = NULL;36   ListNode *t1 = NULL;37   ListNode *t2 = NULL;38   ListNode *node = NULL;39   int len = 0;40         41   node = head;42   while (node && (++len))43     node = node->next;44             45   for (int l = 1; l < len; l <<= 1) {46     prev = NULL;47     h1 = NULL;48     h2 = NULL;49     t1 = NULL;50     t2 = NULL;51     node = head;52             53     while (node) {54       h1 = t1 = node;55       for (int i = 0; node && i < l; i++) {56         t1 = node;57         node = node->next;58       }59       if (t1)60         t1->next = NULL;61       h2 = t2 = node;62       for (int i = 0; node && i < l; i++) {63         t2 = node;64         node = node->next;65       }66       if (t2)67         t2->next = NULL;68                 69       ListNode *h, *t;70       if (h2)71         mergeList(h1, h2, h, t);72       else {73         h = h1;74         t = t1;75       }76       if (!prev)77         head = h;78       else79         prev->next = h;80       t->next = node;81       prev = t;82     }83   }84         85   return head;86 }