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

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

本题目来源于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

{

相关文章
|
存储 缓存 算法
内存分配不再神秘:深入剖析malloc函数实现原理与机制
内存分配不再神秘:深入剖析malloc函数实现原理与机制
|
存储 编译器 C语言
你知道数据在内存中是如何存储的嘛?(二)
你知道数据在内存中是如何存储的嘛?(二)
749 0
|
设计模式 NoSQL Java
通用框架实践|Pipeline设计+幂等重试
本文讲述在闲鱼同城模块中,针对二手车和租房等业务的商业化需求,设计和实现了一个基于Pipeline模式和幂等性控制的通用框架。
|
12月前
|
数据采集 测试技术 Swift
666条数据,训练LongWriter模型,写万字长文!模型&数据集均开源!
大模型的上下文(Context)支持越来越长的背景下,让通用的大模型遵循指令来保障长文本输出的长度,依然是一个挑战。
|
11月前
|
Web App开发 缓存 安全
WIN11 Chrome 双击打不开闪退及Chrome浏览器不能拖拽文件crx
【11月更文挑战第6天】本文介绍了 WIN11 系统中 Chrome 浏览器双击打不开闪退及不能拖拽文件 crx 的原因和解决方法。包括浏览器版本过旧、扩展程序冲突、硬件加速问题、缓存过多、安全软件冲突、系统文件损坏、用户配置文件损坏等问题的解决方案,以及 crx 文件的屏蔽、权限问题和文件格式问题的处理方法。
2784 2
|
12月前
|
人工智能 搜索推荐 安全
人工智能与未来社会:探索AI在教育领域的革命性影响
本文深入探讨了人工智能(AI)技术在教育领域的潜在影响和变革。通过分析AI如何个性化学习路径、提高教学效率以及促进教育资源的公平分配,我们揭示了AI技术对教育模式的重塑力量。文章还讨论了实施AI教育所面临的挑战,包括数据隐私、伦理问题及技术普及障碍,并提出了相应的解决策略。通过具体案例分析,本文旨在启发读者思考AI如何助力构建更加智能、高效和包容的教育生态系统。
|
12月前
|
存储
使用迭代代替递归
使用迭代代替递归
167 3
|
算法 Java C语言
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
246 1
|
网络协议 算法 Linux
TCP是如何进行拥塞控制的?
TCP是如何进行拥塞控制的?
343 1