LeetCode Hot100 排序链表

ops/2024/9/23 7:37:46/

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

示例 1:

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

归并排序

思路

        题目要求O(nlogn)时间复杂度和O(1)空间复杂度,使用归并排序而非是快速排序,归并排序比快排稳定。把链表分割成节点,再合并

代码 

class Solution {
public:ListNode* merge(ListNode* list1, ListNode* list2){ListNode* mergelist = new ListNode(0); ListNode* node = mergelist;while(list1 != nullptr && list2 != nullptr){if(list1->val > list2->val){node->next = list2;list2 = list2->next;}else{node->next = list1;list1 = list1->next;}node = node->next;}if(list1 != nullptr)node->next = list1;else if(list2 != nullptr)node->next = list2;return mergelist->next;}ListNode* sortList(ListNode* head) {     if(head == nullptr || head->next == nullptr)return head;int listlen = 0;ListNode* res = new ListNode(0, head);while(head != nullptr){head = head->next;++listlen;}for(int i=1; i<listlen; i*=2){ListNode* tmp = res->next;ListNode* tail = res;while(tmp != nullptr){ListNode* left = tmp;for(int j=1; j<i && tmp->next!=nullptr; ++j)tmp = tmp->next;ListNode* right = tmp->next;tmp->next = nullptr;tmp = right;for(int j=1; j<i && tmp!=nullptr && tmp->next!=nullptr; ++j)tmp = tmp->next;ListNode* next = nullptr;if(tmp != nullptr){next = tmp->next;tmp->next = nullptr;}tail->next = merge(left, right);while(tail->next != nullptr)tail = tail->next;tmp = next;}}ListNode* secondhead = res->next;delete res;return secondhead;}
};


http://www.ppmy.cn/ops/93497.html

相关文章

常用的数据结构有哪些?

常用的数据结构是计算机科学中用于组织、存储和高效处理数据的基本结构。这些结构的选择取决于具体的应用场景和需要解决的问题。以下是一些最常用的数据结构&#xff1a; 数组&#xff08;Array&#xff09;&#xff1a; 数组是一种基础的数据结构&#xff0c;用于在计算机内存…

JAVA:设计模式的详细指南

请关注微信公众号&#xff1a;拾荒的小海螺 博客地址&#xff1a;http://lsk-ww.cn/ 1、简述 设计模式&#xff08;Design Patterns&#xff09;是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。它们可以帮助开发者以一种更优雅和高效的方式解决常见的…

【微信小程序】网络数据请求

1. 小程序中网络数据请求的限制 2. 配置 request 合法域名 3. 发起 GET 请求 调用微信小程序提供的 wx.request() 方法,可以发起 GET 数据请求,示例代码如下: 4. 发起 POST 请求 调用微信小程序提供的 wx.request() 方法,可以发起 POST 数据请求,示例代码如下: 5. …

8.13网络编程

笔记 多点通信 一、套接字属性 套接字属性的获取和设置 #include <sys/types.h> /* See NOTES */#include <sys/socket.h>int getsockopt(int sockfd, int level, int optname,void *optval, socklen_t *optlen);int setsockopt(int sockfd, int level…

Linux 基本指令讲解

linux 基本指令 clear 清屏 Alt Enter 全屏/退出全屏 pwd 显示当前用户所处路径 cd 改变目录 cd /root/mikecd … 返回上级目录cd - 返回最近所处的路径cd ~ 直接返回当前用户自己的家目 roor 中&#xff1a;/root普通用户中&#xff1a;/home/mike mkdir 创建一个文件夹(d) …

异常信息转储预研笔记-ptrace调试问题

遇到问题&#xff1a; 编写的demo执行在ptrace()函数报错&#xff0c;errno为1&#xff08;EPERM&#xff09;&#xff0c;表示当前进程没有足够的权限来执行所请求的ptrace操作。可能操作系统的安全策略限制了对运行进程跟踪或操作。好无奈。 ptrace(PTRACE_ATTACH, ....) …

【QT 5 QT 6 构建工具qmake-cmake-和-软件编译器MSVCxxxvs MinGWxxx说明】

【QT 5报错&#xff1a;/xxx/: error: ‘class Ui::frmMain’ has no member named ‘xxx’-和-软件编译器MSVCxxxvs MinGWxxx说明】 1、前言2 、qt 中 Qmake CMake 和 QBS1-qmake2-Cmake3-QBS4-官网一些说法5-各自特点 3、软件编译套件1-Desktop Qt 6.7.2 llvm-mingw 64-bit2-…

排序算法之希尔排序

title: 希尔排序 date: 2024-7-25 10:48:15 0800 categories: 排序算法 tags:排序算法希尔排序 description: 1959年Shell发明&#xff0c;是简单插入排序的改进版。是一种高效的排序算法&#xff0c;通过分组和逐步缩减增量&#xff0c;使得数组在接近有序的情况下进行最终排…