Leetcode148. 排序链表(HOT100)

server/2024/11/26 19:21:47/

链接

我写的错误代码:

class Solution {
public:ListNode* sortList(ListNode* head) {if (!head || !head->next)return head;ListNode* fast = head;ListNode* slow = head;while (fast&&fast->next) {fast = fast->next->next;slow = slow->next;}ListNode* p = sortList(head);ListNode* q = sortList(slow);return merge(p, q);}ListNode* merge(ListNode* p, ListNode* q) {ListNode* head = new ListNode(-1);while (p && q) {if (p->val <= q->val) {ListNode* cur = p->next;p->next = head->next;head->next = p;p = p->next;} else {ListNode* cur = q->next;q->next = head->next;head->next = q;q = q->next;}}ListNode* tail = head;while (tail->next) {tail = tail->next;}tail->next = p ? p : q;return head->next;}
};

 正确代码如下:

/*** 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 n = 0;for(auto p = head;p;p = p->next)++n;for(int i = 1;i<n;i*=2){//刚开始每段只有一个节点,最后一次每段有大约一半节点,合并成最后的答案auto dummy = new ListNode(-1),cur = dummy;for(int j = 1;j<=n;j+=i*2){auto p = head,q = p;for(int k = 0;k<i&&q;k++) q = q->next;auto o = q;for(int k = 0;k<i&&o;k++)o = o->next;int l = 0,r = 0;while(l<i && r<i && p && q){if(p->val<=q->val)cur = cur->next = p,p = p->next,l++;else cur = cur->next = q,q = q->next,r++;}while(l<i && p){cur = cur->next = p;p = p->next;l++;}while(r<i && q){cur = cur->next = q;q = q->next;r++;}head = o;}cur->next = nullptr;head = dummy->next;dummy->next = nullptr;//delete dummy;//}return head;}
};

这是自底向上归并排序写法。 

图示:

 

上图cur也要跟随移动。

 

 

 

 

第二轮:
 

 

 

总体图示就这样的。q是依靠p推出来的,刚开始跳1步,然后跳2步........

o是为了记录下一次应该继续排序的位置。

dummy是一个虚拟头结点,cur用来维护它的尾,至于谁往cur->next插入,要看p q指向的节点谁的值小。

每一轮完了后,让head重新回归dummy的next,然后cur->next=nullptr;即将尾置空。

 

 

 

 


http://www.ppmy.cn/server/145130.html

相关文章

Spring Boot 3.0废弃了JavaEE,改用了Jakarta EE

Spring Boot 3.0废弃了JavaEE&#xff0c;改用了Jakarta EE 历史背景 javax变成Jakarta的主要原因是因为Java EE项目从Oracle转移到了Eclipse Foundation&#xff0c;并改名为Jakarta EE。 JavaEE是从Java 1.2版本开始推出的Java企业级开发平台&#xff0c;最初的名称是J2EE(J…

电脑的ip地址怎么换掉:全面指南

在数字化时代&#xff0c;电脑已成为我们日常生活和工作中不可或缺的一部分。而IP地址&#xff0c;作为电脑在网络世界中的唯一身份标识&#xff0c;其重要性不言而喻。有时&#xff0c;出于安全、隐私或访问特定资源的需要&#xff0c;我们可能需要更换电脑的IP地址。本文将详…

React表单联动

Ant Design 1、dependencies Form.Item 可以通过 dependencies 属性&#xff0c;设置关联字段。当关联字段的值发生变化时&#xff0c;会触发校验与更新。 一种常见的场景&#xff1a;注册用户表单的“密码”与“确认密码”字段。“确认密码”校验依赖于“密码”字段&#x…

簡單易懂:如何在Windows系統中修改IP地址?

無論是為了連接到一個新的網路&#xff0c;還是為了解決網路連接問題&#xff0c;修改IP地址都是一個常見的操作。本文將詳細介紹如何在Windows系統中修改IP地址&#xff0c;包括靜態IP地址的設置和動態IP地址的獲取。 IP地址是什麼&#xff1f; IP地址是互聯網協議地址的簡稱…

【 模型】 开源图像模型Stable Diffusion入门手册

开源图像模型Stable Diffusion入门手册 引言硬件要求环境部署手动部署整合包 模型装配更新显存优化插件配置文生图最简流程提示词使用技巧结语 引言 Stable Diffusion是一款在2022年发布的深度学习文字到图像生成模型。它能够根据文字描述生成详细的图像&#xff0c;并且在几秒…

ddddocr:强大的开源OCR库(2.0版本)

ddddocr&#xff1a;强大的开源OCR库&#xff08;2.0版本&#xff09; ddddocr 是一款基于深度学习的开源 OCR&#xff08;光学字符识别&#xff09;库&#xff0c;旨在高效识别各种验证码。随着版本更新&#xff0c;ddddocr 的功能不断增强&#xff0c;特别是2.0版本在准确率…

[Unity Demo]从零开始制作空洞骑士Hollow Knight第二十集:制作专门渲染HUD的相机HUD Camera和画布HUD Canvas

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、制作HUD Camera以及让两个相机同时渲染屏幕二、制作HUD Canvas 1.制作法力条Soul Orb引入库2.制作生命条Health读入数据3.制作吉欧统计数Geo Counter4.制作…

云服务器部署WebSocket项目

WebSocket是一种在单个TCP连接上进行全双工通信的协议&#xff0c;其设计的目的是在Web浏览器和Web服务器之间进行实时通信&#xff08;实时Web&#xff09; WebSocket协议的优点包括&#xff1a; 1. 更高效的网络利用率&#xff1a;与HTTP相比&#xff0c;WebSocket的握手只…