leetcode-148. 排序链表(链表排序)

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：


输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：


输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]
 

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution { 

public:
ListNode* sortList(ListNode* head) { 

int num = 0;
ListNode * pp = head;
while(pp)pp = pp->next,num ++;
ListNode *last = NULL;
int l = 0;
ListNode *p1 = NULL,*p2 = NULL,*p = NULL,*pt = NULL,*ptt = NULL;
ListNode *p1e = NULL,*p2e = NULL;
ListNode *t = new ListNode();
for(int len = 2;len < 2 * num;len *= 2){ 

bool start = true;
p = head;
last = NULL;
for(int i = 0;i < (num + len - 1)/ len;i ++){ 

l = 0;
p1 = p2 = NULL;
p1 = p;
pt = t;
p1e = p2e = NULL;
ptt = pt;
while(p){ 

p = p->next;
l ++;
if(l == len / 2){ 

p1e = p;
p2 = p;
}
if(l == len){ 

p2e = p;
break;
}
}
while(p1 && p2 && p1 != p1e && p2 != p2e){ 

if(p1->val < p2->val)pt->next = p1,pt=pt->next,p1=p1->next;
else pt->next = p2,pt=pt->next,p2=p2->next;
}
while(p1 && p1 != p1e){ 

pt->next = p1;
pt=pt->next;
p1=p1->next;
}
while(p2 && p2 != p2e){ 

pt->next = p2;
pt=pt->next;
p2 = p2->next;
}
if(start)head = ptt->next,start = false;
if(last != NULL)last->next = ptt->next;
last = pt;
}
pt->next = NULL;
}
return head;
}
};