Leetcode148 排序链表
148. 排序链表 - 力扣（LeetCode）
class Solution {
public:
ListNode* sortList(ListNode* head) {
int n = 0;
for(ListNode *cur = head; cur;cur = cur->next) n++; //链表长度
for(int i = 1; i < n; i *= 2) // 代表层次数
{
ListNode *dummy = new ListNode(0), *cur = dummy;
int cnt =ceil(1.0 *n/(2*i)); //向上取整 cnt = ceil(1.0 *5 /（2*1）) = 3
while(cnt--) //cnt 代表每一层 两两合并次数
{
//链表A的头结点为p
//链表B的头结点为q （p在q前 q是p的下一个链表）
//链表A B合并
ListNode *p = head, *q = head;
for(int j = 0; j <i && q;j++) q = q->next; //得到B节点的头节点q
ListNode *next = q; //next 下一对 A,B的起始节点
for(int j = 0;j < i && next;j++) next = next->next; //得到下一对A,B节点的起始节点
int l = 0, r = 0;
while(l < i && r < i && q && p) //合并A，B链表
{
if(p->val <= q->val)
{
cur->next = p ;
cur = cur->next;
p = p->next;
l++;
}
else
{
cur->next = q ;
cur = cur->next;
q = q->next;
r++;
}
}
while(l < i && p) cur = cur->next= p,p =p->next,l++;
while(r < i &&q) cur =cur->next =q, q = q->next,r++;
head = next; //更新head
}
cur->next = nullptr;
head = dummy->next;
}return head;
}
};