C++速通LeetCode中等第21题-排序链表（空间O(1)）

class Solution{
public:
	ListNode* sortList(ListNode* head){
		ListNode *h, *h1, *h2, *pre, *res; 
		//利用h找到该次归并的下一组起点，h1为当前归并组的左起点，h2为右起点
		//pre作为每次归并的虚设头结点，res为最终结果的虚设头结点 
		
		int len = 0;
		h = head;
		while(h){ //计算链表长度 
			len++;
			h = h->next;
		}
		
		int curr_len = 1; //当前归并目标的长度，当=length时归并结束 
		
		res = new ListNode(0);
		res->next = head;
		
		while(curr_len < len){
			pre = res;
			h = pre->next;
			while(h){ //当前长度的归并过程，h为空说明所有结点都遍历完成 
				int i = curr_len; //寻找左起点和右起点 
				h1 = h; //左起点 
				
				while(i>0 && h){
					i--;
					h = h->next;
				}
				if(i>0){ //若由于h为空退出循环，即未找到右起点就已经无剩余结点，那么归并完成 
					break;
				}
				h2 = h; //右起点 
				
				i = curr_len;
				int num2 = 0;
				while(i>0 && h){ //将h移动到该次归并下一组的起点 
					i--;
					h = h->next;
					num2++;
				}
				
				int num1 = curr_len;
				while(num1 > 0 && num2 > 0){ //归并 
					if(h1->val <= h2->val){
						pre->next = h1;
						h1 = h1->next;
						num1--;	
					}
					else{
						pre->next = h2;
						h2 = h2->next;
						num2--;
					}
					
					pre = pre->next; 
				}
				
				if(num1>0){
					pre->next = h1;
				}
				else if(num2>0){
					pre->next = h2;
				}
				
				while(num1>0 || num2>0){//移动到该组末尾 
					pre = pre->next;
					num1--;
					num2--;
				}
				
				pre->next = h; //连接下一组的起点 
			}
			
			curr_len *= 2;
		}
		
		
		return res->next;
	}
			
};