LeetCode148. Sort List 单链表排序
2022/7/3 23:23:00
本文主要是介绍LeetCode148. Sort List 单链表排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
单链表排序
以arr = [8,6,7,5,1,2]为例
1. 自顶向下归并排序(递归)——分治法
Time: O(NlogN)
Space: O(LOG(N))
- 自顶向下:
(8->6->7) | (5->1->2)
(8->6)|(7) | (5->1)|(2)
(8)|(6)|(7) |(5)|(1)|(2)
- 栈返回:
(6->8)|(7) |(1->5) | (2)
(6->7->8) | (1->2->5)
(1->2->5->6->7->8)
/** * 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) { if(!head || !head->next){ return head; } ListNode* slow = head, *fast = head; while(fast->next && fast->next->next){ slow = slow->next; fast = fast->next->next; } ListNode* right = slow->next; slow->next = nullptr; ListNode* left = head; ListNode* sortedLeft = sortList(left), *sortedRight = sortList(right); return merge(sortedLeft, sortedRight); } ListNode* merge(ListNode* left, ListNode* right){ ListNode dummyNode(0), *cur = &dummyNode; while(left && right){ if(left->val < right->val){ cur->next = left; left = left->next; cur = cur->next; }else{ cur->next = right; right = right->next; cur = cur->next; } } cur->next = left ? left : right; return dummyNode.next; } };
2. 自底向上归并排序 (空间O(1))
Time: O(NLogN)
Space: O(1)
- 切分归并过程
step = 1: dummy->(8->6->7->5->1->2)
step = 1: dummy->(6->8) | (7->5->1->2)
step = 1: dummy->(6->8->5->7) (1->2)
step = 1: dummy->(6->8->5->7->1->2)
step = 2: dummy->(5->6->7->8) | (1->2)
...
dummy->(1->2->5->6->7->8)
- 返回 dummy->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) { if(!head || !head->next){ return head; } int length = 0; ListNode* cur = head; while(cur){ cur = cur->next; length++; } ListNode newNode(0); newNode.next = head; for(int step = 1; step < length; step <<= 1){ ListNode* pre = &newNode; cur = newNode.next; while(cur){ ListNode* left = cur; ListNode* right = cutList(left, step); cur = cutList(right, step); pre->next = mergeList(left, right); while(pre->next){ pre = pre->next; } } } return newNode.next; } ListNode* cutList(ListNode* cur, int step){ for(int i = 1; (i < step) && cur; ++i){ cur = cur->next; } if(!cur) return nullptr; ListNode* nextNode = cur->next; cur->next = nullptr; return nextNode; } ListNode* mergeList(ListNode* left, ListNode* right){ ListNode dummyNode(0), *cur = &dummyNode; while(left && right){ if(left->val < right->val){ cur->next = left; left = left->next; }else{ cur->next = right; right = right->next; } cur = cur->next; } cur->next = left ? left : right; return dummyNode.next; } };
3. 快速排序(元素个数较多且基本有序的情况下可能超时)
Time: worst case, O(N^2)
Space: O(N)
/** * 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) { ListNode dummyNode(0); dummyNode.next = head; quickSort(&dummyNode, head, nullptr); return dummyNode.next; } void quickSort(ListNode* dummyNode, ListNode* head, ListNode* end){ if(head != end){ ListNode* pivot = getPivot(dummyNode, head); quickSort(dummyNode, dummyNode->next, pivot); quickSort(pivot, pivot->next, end); } } ListNode* getPivot(ListNode* dummyNode, ListNode* head){ ListNode nodeR(0), nodeL(0); ListNode* cur = head->next, *pRight = &nodeR, *pLeft = &nodeL; int pivot = head->val; while(cur){ if(cur->val < pivot){ pLeft->next = cur; pLeft = pLeft->next; }else{ pRight->next = cur; pRight = pRight->next; } cur = cur->next; } pRight->next = nullptr; head->next = nodeR.next; pLeft->next = head; dummyNode->next = nodeL.next; return dummyNode->next; } };
这篇关于LeetCode148. Sort List 单链表排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升