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;
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

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

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • Java 集合

    Java 集合

    2021年10月7日
    38
  • ubuntu上安装pycharm_ubuntu打开pycharm

    ubuntu上安装pycharm_ubuntu打开pycharm一、安装python3.5默认情况下,linux下是默认使用2.x版本的,现在我们要安装3.x版本,具体操作如下1、去官网下载安装包。(这里我下载的是.tgz版本)2、用命令解压安装包tar-zxvf+压缩包3、进入解压后的文件cd+解压后的文件夹4、./configure–prefix=/usr/local/python3.5重定向到该文件夹下进行编译5.make6.make…

    2022年8月29日
    1
  • qq视频资源是什么_qq代码视频教程

    qq视频资源是什么_qq代码视频教程QQ视频资源裂变源码有哪些功能对于2021年网赚引流最快变现的一些思路qq资源!已解锁全部!点击进入观赏!这个是分享以后得卡片标题内容这个系统有2个版本,第一调用单个视频资源链接(支持mp4,m3u8格式),第二个版本支持观看10-60秒后强制分享弹窗下上图片位置带自定义图片广告跳转,跳转链接可批量留多个裂变网页链接达到裂变式框架“`…

    2022年8月24日
    7
  • rabbitmq下载安装教程_rabbitmq官方教程中文

    rabbitmq下载安装教程_rabbitmq官方教程中文RabbitMq安装教程RabbitMq简介安装准备工具RabbitMq简介##1.1消息队列中间件简介消息队列中间件是分布式系统中重要的组件,主要解决应用耦合,异步消息,流量削锋等问题实现高性能,高可用,可伸缩和最终一致性[架构]使用较多的消息队列有ActiveMQ(安全),RabbitMQ,ZeroMQ,Kafka(大数据),MetaMQ,RocketMQ以下介绍消息队列在实际应用中常用的使用场景:异步处理,应用解耦,流量削锋和消息通讯四个场景1.2什么是RabbitMQ RabbitM

    2022年10月3日
    0
  • LWIP使用解析_lwip tcp

    LWIP使用解析_lwip tcp1:环境STM32F407RT-thread2:结构体使用最上层:structrt_stm32_ethstructrt_stm32_eth{/*inheritfromethernetdevice*/structeth_deviceparent;/*interfaceaddressinfo,hwaddress*/rt_uint8_tdev_addr[MAX_ADDR_LEN];/*ETH_Speed*/

    2022年10月30日
    0
  • 捷达vs7与VS5是一个平台打造_visual studio没有控制台应用程序

    捷达vs7与VS5是一个平台打造_visual studio没有控制台应用程序我正在使用VisualStudioTeamServices(是VSOnline)。我从VisualStudio2013升级到了VisualStudio2015。当我打开源代码管理项目时,出现以下错误:您已加载的解决方案已绑定到https://xx.visualstudio.com/defaultcollection上的源控制服务器,但该服务器上没有任何工作空间可以找到服务器。如果您确…

    2022年8月12日
    6

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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