川畅科技网站设计,如何推广网站方法,如何开科技软件,平面设计网上怎么接单算法-堆/归并排序-排序链表
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/sort-list/description/?envTypestudy-plan-v2envIdtop-interview-150
1.2 题目描述 2 优先级队列构建大顶堆
2.1 思路
优先级队列构建小顶堆链表所有元素放入小顶堆依次取出堆顶…算法-堆/归并排序-排序链表
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/sort-list/description/?envTypestudy-plan-v2envIdtop-interview-150
1.2 题目描述 2 优先级队列构建大顶堆
2.1 思路
优先级队列构建小顶堆链表所有元素放入小顶堆依次取出堆顶元素链表串起来即可
2.2 代码
class Solution {public ListNode sortList(ListNode head) {if (head null) {return null;}PriorityQueueListNode minHeap new PriorityQueue((n1,n2)-n1.val-n2.val);ListNode newHead new ListNode();while(null ! head) {minHeap.add(head);head head.next;}ListNode tmp minHeap.poll();tmp.next null;newHead.next tmp;while(minHeap.size()0) {ListNode cur minHeap.poll();tmp.next cur;tmp cur;tmp.next null;}return newHead.next;}
}2.3 时间复杂度
O(nlogn)
2.4 空间复杂度
O(n)
3 归并排序
3.1 思路
用快慢指针法找到链表中间位置将链表拆分成两条子链表对子链表分别排序将排序后的子链表合并排序
3.2 代码
class Solution {public ListNode sortList(ListNode head) {if (null head) {return null;}if (null head.next) {return head;}ListNode fast head.next;ListNode slow head;// 找到fast到中间位置while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}// 切断两个链表fast slow.next;slow.next null;// 分别对两个子链表排序slow sortList(head);fast sortList(fast);ListNode dummy new ListNode();head dummy;// 合并已排序的两个子链表while (null ! slow null ! fast) {if (slow.val fast.val) {head.next slow;slow slow.next;} else {head.next fast;fast fast.next;}head head.next;}while (null ! slow) {head.next slow;slow slow.next;head head.next;}while (null ! fast) {head.next fast;fast fast.next;head head.next;}return dummy.next;}
}3.3 时间复杂度 O(nlogn)
3.4 空间复杂度
O(logn)调用栈深度
4 非递归方式循环
4.1 思路
3中使用递归方式空间复杂度O(logn)可改为循环方式达到O(1)的空间复杂度
4.2 代码 4.3 时间复杂度
4.4 空间复杂度
参考文档
Sort List 归并排序链表
