商城网站开发视频教程,重庆施工员证书查询网,北京平台网站建设公司,源码超市网站源码文章目录1. 题目2. 解题2.1 归并排序2.2 快速排序1. 题目
在 O(n log n) 时间复杂度和常数级空间复杂度下#xff0c;对链表进行排序。
示例 1:输入: 4-2-1-3
输出: 1-2-3-4
示例 2:输入: -1-5-3-4-0
输出: -1-0-3-4-对链表进行排序。
示例 1:输入: 4-2-1-3
输出: 1-2-3-4
示例 2:输入: -1-5-3-4-0
输出: -1-0-3-4-5来源力扣LeetCode 链接https://leetcode-cn.com/problems/sort-list 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 归并排序
参考单链表归并排序
class Solution {
public:ListNode* sortList(ListNode* head) {if(head NULL || head-next NULL)return head;ListNode *fast head-next, *slow head, *rightHead;//fast初始化先走一步偶数个链表时防止一边0个一边2个节点while(fast fast-next){fast fast-next-next;slow slow-next;}rightHead slow-next;slow-next NULL;//先断开再操作左右ListNode *right sortList(rightHead);ListNode *left sortList(head);return merge(left, right);}ListNode* merge(ListNode *left, ListNode *right) {ListNode *emptyHead new ListNode(0);//虚拟哨兵头ListNode *cur emptyHead;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 NULL ? right : left);cur emptyHead-next;delete emptyHead;return cur;}
};2.2 快速排序
class Solution {
public:ListNode* sortList(ListNode *head) {quicksort(head, NULL);return head;}void quicksort(ListNode *head, ListNode *tail) {if(head tail || head-next NULL)return;ListNode *mid partition(head,tail);quicksort(head, mid);quicksort(mid-next, tail);}ListNode* partition(ListNode *head, ListNode *tail){int pivot head-val;ListNode *left head, *cur head-next;while(cur ! NULL cur ! tail){if(cur-val pivot){left left-next;swap(cur-val, left-val);}cur cur-next;}swap(left-val, head-val);return left;}
};
