算法-堆/归并排序-排序链表
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150
1.2 题目描述
2 优先级队列构建大顶堆
2.1 思路
- 优先级队列构建小顶堆
- 链表所有元素放入小顶堆
- 依次取出堆顶元素,链表串起来即可
2.2 代码
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return null;
}
PriorityQueue<ListNode> 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)调用栈深度文章来源:https://www.toymoban.com/news/detail-723304.html
4 非递归方式(循环)
4.1 思路
3中使用递归方式,空间复杂度O(logn),可改为循环方式达到O(1)的空间复杂度文章来源地址https://www.toymoban.com/news/detail-723304.html
4.2 代码
4.3 时间复杂度
4.4 空间复杂度
参考文档
- Sort List (归并排序链表)
到了这里,关于算法-堆/归并排序-排序链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!