算法-堆/归并排序-排序链表
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)调用栈深度
4 非递归方式(循环)
4.1 思路
3中使用递归方式,空间复杂度O(logn),可改为循环方式达到O(1)的空间复杂度
4.2 代码
4.3 时间复杂度
4.4 空间复杂度
参考文档
- Sort List (归并排序链表)