大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168551.html原文链接：https://javaforall.net
