例如:

list             1 3 5 7 9 2 4 6 8 

 

level[20]    20层

 

1.   level[0]   1

2.   level[0]   NULL

      level[1]   1 3 

3    level[0] 5

      level[1] 1 3

4    level[0] NULL

      level[1] NULL

      level[2] 1 3 5 7

5    level[0] 9

      level[1] NULL

      level[2] 1 3 5 7

6    level[0] NULL

      level[1] 2 9

      level[2] 1 3 5 7

7    level[0] 4

      level[1] 2 9

      level[2] 1 3 5 7

8    level[0] NULL

      level[1] NULL

      level[2] NULL

     level[3]  1 2 3 4 5 6 7 9

9   level[0] 8

      level[1] NULL

      level[2] NULL

     level[3]  1 2 3 4 5 6 7 9

 

最后再一次总的归并

1 2 3 4 5 6 7 8 9 

 

class Solution {public:	ListNode* level[20];	ListNode* sortList(ListNode* head) {		if (head == NULL)return NULL;		ListNode* cur = head;		while (cur != NULL)		{			int i = 0;			ListNode* cc = cur;			cur = cur->next;			cc->next = NULL;			while (level[i] != NULL) {				//归并level[i]和cc				cc = mar(level[i], cc);				level[i] = NULL;				i++;			}			level[i] = cc;		}		vector
     
       lev;		for (int i = 0; i < 20; i++)		{			if (level[i])				lev.push_back(i);		}		for (int i = 1; i < lev.size(); i++)		{			level[lev[0]] = mar(level[lev[0]], level[lev[i]]);		}		return level[lev[0]];	}        //归并a,b	ListNode* mar(ListNode* a, ListNode* b) {		ListNode ret(0);		ListNode* cur = &ret;		while (a || b)		{			if (a && b)			{				bool alessb = (a->val < b->val);				cur->next = alessb ? a : b;				if (alessb)					a = a->next;				else					b = b->next;				cur = cur->next;			}			else if (a)			{				cur->next = a;				cur = cur->next;				a = a->next;			}			else {				cur->next = b;				cur = cur->next;				b = b->next;			}		}		cur->next = NULL;		return ret.next;	}};