程序员必知:单链表排序(快速排序、归并排序)

简介: 程序员必知:单链表排序(快速排序、归并排序)

本题目来源于LeetCode,具体如下:

Sort a linked list in O(n log n) time using constant space complexity.

题目要求复杂度O(nlogn),因此我们很自然考虑使用快速排序或者归并排序,但是后来经过实践证明,使用快速排序总是AC超时,归并排序则可以正确AC。

分析一下原因,个人认为是与测试数据有关,因为快速排序不能保证算法复杂度一定是O(nlogn),当数据比较集中时,即使做随机选取key值,算法的复杂度也非常接近O(N^2),因此会出现超时,所以考虑使用归并排序。

下面是采用归并排序的思路已经AC代码:

主要考察3个知识点,

知识点1:归并排序的整体思想

知识点2:找到一个链表的中间节点的方法

知识点3:合并两个已排好序的链表为一个新的有序链表

归并排序的基本思想是:找到链表的middle节点,然后递归对前半部分和后半部分分别进行归并排序,最后对两个以排好序的链表进行Merge。

【cpp】 view plain copy

#include

#include

#include

#include

#include

#include

using namespace std;

struct ListNode {

int val;

ListNode next;

ListNode(int x) : val(x), next(NULL) {}

};

class Solution {

public:

ListNode mergeLists(ListNode a, ListNode b) //合并两个已经排序的链表

{

if (a == NULL) return b ;

if (b == NULL) return a ;

ListNode ret = NULL ;

ListNode tail = NULL ;

ret = new ListNode(-1) ;

tail = ret ;

while (a b)

if (a->val val)

{

tail->next = a ;

tail = tail->next ;

a = a->next ;

}

else

{

tail->next = b ;

tail = tail->next ;

b = b->next ;

}

if (a)

tail->next = a ;

if (b)

tail->next = b ;

ListNode del = ret ;

ret = ret->next ;

delete del ;

return ret ;

}

ListNode getMid(ListNode head) //得到中间节点

{

if (!head) return NULL ;

if (!head->next) return head ;

ListNode slow = head ;

ListNode fast = head->next ;

while (fast fast->next)

{

slow = slow->next ;

fast = fast->next->next ;

}

return slow ;

}

ListNode sortList(ListNode head) { //合并排序

if (!head) //代码效果参考:http://www.zidongmutanji.com/bxxx/437098.html

return NULL ;

if (!head->next) return head ;

ListNode mid = getMid(head) ;

ListNode nextPart = NULL ;

if (mid)

{

nextPart = mid->next ;

mid->next = NULL ;

}

return mergeLists(

sortList(head) ,

sortList(nextPart)

) ;

}

};

void insertBack(ListNode head, ListNode tail, ListNode n) //从尾部插入

{

if (n)

{

if (head == NULL)

{

head = n ;

tail = n ;

}

else

{

(tail)->next = n ;

tail = n ;

}

}

}

int main(int argc, char** argv)

{

ifstream in("data.txt") ;

ListNode head = NULL ;

ListNode //代码效果参考:http://www.zidongmutanji.com/zsjx/395573.html

tail = NULL ;

int val ;

Solution s ;

while(in ] val)

{

ListNodetmp = new ListNode(val) ;

insertBack(head, tail, tmp) ;

}

head = s.sortList(head) ;

while(head)

{

cout [ head->val [ " " ;

head = head->next ;

}

cout [ endl ;

return 0 ;

}

下面再说一下自己AC超时的代码吧,

这里我尝试了两种实现方案:

第一种是:

在找划分点的过程中,维护连个链表Left 和Right 所有不大于key的元素都链到Left上,大于key的链到Right上,最后再将Left, key , Right三部分连接起来。

代码如下:

【cpp】 view plain copy

#include

#include

#include

#include

#include

#include

using namespace std;

struct ListNode {

int val;

ListNode next;

ListNode(int x) : val(x), next(NULL) {}

};

class Solution {

public:

inline void insertBack(ListNode head, ListNode tail, //代码效果参考:http://www.zidongmutanji.com/zsjx/213875.html

ListNode n) //从尾部插入

{

if (n)

{

if (head == NULL)

{

head = n ;

tail = n ;

}

else

{

(tail)->next = n ;

tail = n ;

}

}

}

ListNode sortList(ListNode head) {

if (!head) return NULL ;

if (head->next == NULL) return head ;

//划分

ListNode tmpNode = head ;

head = head->next ;

ListNode sleft = NULL , eleft = NULL ;

ListNode sright = NULL , eright = NULL ;

while (head)

{

ListNode insNode = head ;

head = head->next ;

insNode->next = NULL ;

if (insNode->val > tmpNode->val)

insertBack(sright, eright, insNode) ;

else

insertBack(sleft, eleft, insNode) ;

}

//递归调用

sleft = sortList(sleft) ;

sright = sortList(sright) ;

//下面三句话第一次没有加上,调试了一下午才找到原因

eleft = sleft ;

if (eleft)

{

while(eleft->next)

eleft = eleft->next ;

}

//拼接起来

if (eleft)

{

head = sleft ;

eleft->next = tmpNode ;

}

else

head = tmpNode ;

tmpNode->next = sright ; //连接起来

//返回结果

return head ;

}

};

int main(int argc, char** argv)

{

ifstream in("data.txt") ;

ListNode head = NULL ;

ListNode tail = NULL ;

int val ;

Solution s ;

while(in ] val)

{

ListNodetmp = new ListNode(val) ;

s.insertBack(head, tail, tmp) ;

}

head = s.sortList(head) ;

while(head)

{

cout [ head->val [ " " ;

head = head->next ;

}

cout [ endl ;

return 0 ;

}

第二种方案:使用快排的另一种思路来解答。我们只需要两个指针p和q,这两个指针均往next方向移动,移动的过程中保持p之前的key都小于选定的key,p和q之间的key都大于选定的key,那么当q走到末尾的时候便完成了一次划分点的寻找。如下图所示:

实现代码如下:

【cpp】 view plain copy

#include

#include

#include

#include

#include

#include

using namespace std;

struct ListNode {

int val;

ListNode next;

ListNode(int x) : val(x), next(NULL) {}

};

class Solution {

public:

ListNode getPartation(ListNode start, ListNode end)

{

if (start == end) return start ;

ListNode p1 = start ;

ListNode p2 = p1->next ;

int key = start->val ;

while(p2 != end)

{

if (p2->val < key)

{

p1 = p1->next ;

swap(p1->val, p2->val) ; //找到一个比key小的数字,与p1到p2间的数交换,

} //这之间的数都大于等于key

p2 = p2->next ;

}

swap(start->val, p1->val) ; //找到划分位置

return p1 ;

} ;

void QuickSort(ListNode start, ListNode end)

{

if (start != end)

{

ListNode pt = getPartation(start, end) ;

QuickSort(start, pt) ;

QuickSort(pt->next, end) ;

}

}

ListNode sortList(ListNode head) {

QuickSort(head, NULL) ;

return head ;

}

};

void insertBack(ListNode head, ListNode tail, ListNode n) //从尾部插入

{

if (n)

{

if (head == NULL)

{

head = n ;

*tail = n ;

}

else

{

相关文章
|
SQL 数据库 数据库管理
【SQL server】玩转SQL server数据库:第三章 关系数据库标准语言SQL(一)模式、表、索引与视图
【SQL server】玩转SQL server数据库:第三章 关系数据库标准语言SQL(一)模式、表、索引与视图
339 11
|
10月前
|
机器学习/深度学习 人工智能 安全
合合信息在视觉内容安全领域的创新与应用-应对伪造挑战的前沿进展
在2024年中国图象图形学学会青年科学家会议上,上海合合信息科技股份有限公司图像算法研发总监郭丰俊博士分享了“视觉内容安全技术的前沿进展与应用”。随着AI技术的发展,尤其是深度学习和生成对抗网络(GANs)的成熟,视觉内容伪造技术日益复杂,给传统审核手段带来挑战。郭博士介绍了合合信息在图像、视频篡改检测及人脸鉴伪等领域的创新解决方案,强调了大模型如ForgeryGPT的应用前景,并指出未来视觉内容安全将趋向多模态检测和智能化防护,以应对不断演化的伪造手段。合合信息通过自研AI算法,实现了对篡改区域的精确识别,具备较强的跨域泛化能力,已在金融、政府监管等领域广泛应用。
|
缓存 JavaScript
【Node】node.js安装与配置(详细步骤)
【Node】node.js安装与配置(详细步骤)
4546 2
|
11月前
|
消息中间件 NoSQL Redis
【赵渝强老师】Redis的消息发布与订阅
本文介绍了Redis实现消息队列的两种场景:发布者订阅者模式和生产者消费者模式。其中,发布者订阅者模式通过channel频道进行解耦,订阅者监听特定channel的消息,当发布者向该channel发送消息时,所有订阅者都能接收到消息。文章还提供了相关操作命令及示例代码,展示了如何使用Redis实现消息的发布与订阅。
304 0
|
SQL 自然语言处理 数据库
DAIL-SQL: 发掘LLM的NL2SQL能力
最近,DAIL-SQL在魔搭创空间上线,并在NL2SQL任务上取得了新的SOTA。DAIL-SQL可以更好地利用LLM的NL2SQL能力,本文对其进行详细解读。
|
前端开发
前端基础(十二)_overflow属性、clear属性、vertical-align属性
本文详细介绍了CSS中的overflow属性、clear属性和vertical-align属性的用法和效果,并通过实例展示了如何控制元素内容溢出时的显示方式、清除浮动以及对齐行内元素和行内块元素。
1093 1
|
SQL 关系型数据库 MySQL
乐观锁在分布式数据库中与事务隔离级别结合使用
乐观锁在分布式数据库中与事务隔离级别结合使用
216 3
|
定位技术 图形学
【Unity实战】零代码实现物理2d绳子和绳桥效果——Hinge Joint 2D的使用
【Unity实战】零代码实现物理2d绳子和绳桥效果——Hinge Joint 2D的使用
1225 0
基于IEEE13电网系统HIF模型的simulink建模与仿真
**摘要:** 构建基于IEEE13节点的HIF模型Simulink仿真,模拟谐波影响。系统设定为110V/60Hz,使用MATLAB2022a。HIF模型在节点注入谐波,分析其在电网中的传播。故障电流计算公式涉及相电压、地电压和故障阻抗。系统响应通过频率域分析,利用卷积计算X(f)=S(f)*G(f),检测HIF事件。研究旨在改进故障检测,应对传统保护策略失效的情况。
|
程序员 编译器 C++
C++ 新特性 static_assert
C++ 新特性 static_assert
147 1