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

leetcode-148. 排序链表(链表排序)给你链表的头结点 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 &lt

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168551.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号