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;
}
};
