题解 | #单链表的排序#堆排序最简单而直接
默认你已经理解题意
思路如下
堆排序-简单直接
- 定义类型为ListNode的最小堆
- 建堆：链表所有node入堆
- 依次弹出堆顶node，即是从小到大的顺序
- 时间复杂度O(nlogn)，空间复杂度O(n)
- 此法和数组的堆排序几乎没有区别，实现起来最简单，不易出错
class Solution {
public ListNode sortList(ListNode head) {
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((a,b)->a.val-b.val);
while(head!=null)
{
heap.offer(head);
head=head.next;
}
ListNode dummy=new ListNode();
ListNode cur = dummy;
while(heap.size()>0)
{
cur.next=heap.peek();
heap.poll();
cur=cur.next;
}
cur.next=null;
return dummy.next;
}
}
空间复杂度降低-归并
- 数组的归并排序需要引入辅助数组用于归并，因此空间复杂度是O(n)
- 有序链表的归并不需要额外空间辅助
- 自顶向下，对链表进行排序：
- 若链表元素为1或0：
- 已经有序，返回头结点
- 否则
- 用快慢指针法将链表分为两部分，其长度差不超过1
- 对这两部分链表排序（递归）
- 合并排序后的两个链表
- 时间复杂度是O(nlogn)，空间复杂度是O(logn)，即递归调用的深度
public class Solution {
public ListNode SortList(ListNode head) {
if(head==null || head.next==null) return head;
var secondHead = Split(head);
head=SortList(head);
secondHead=SortList(secondHead);
return Merge(head,secondHead);
}
ListNode Merge(ListNode head1, ListNode head2)
{
var dummy=new ListNode(0);
var cur=dummy;
while(head1!=null&&head2!=null)
{
if(head1.val<=head2.val)
{
cur.next=head1;
head1=head1.next;
}
else
{
cur.next=head2;
head2=head2.next;
}
cur=cur.next;
}
if(head1!=null) cur.next=head1;
else cur.next=head2;
return dummy.next;
}
ListNode Split(ListNode head)
{
ListNode slow=head, fast=head.next;
while(fast!=null&&fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
}
var newHead = slow.next;
slow.next=null;
return newHead;
}
}
空间复杂度再降低-自底向上的归并
-
熟悉归并排序的兄弟应该知道，若采用自下而上的归并，可以把递归调用改为迭代的，不使用额外空间
-
但是对于链表来讲，可以把只有1个节点的链表看成有序的，即归并的底
-
两个长度为1的链表合并为长度为2的有序链表，那么两个长度为2的链表合并为长度为4的有序链表，以此类推
-
现在我们设归并长度是len，当然一开始len=1，每进行一轮归并，len*=2，当len>=原始链表长度的时候，链表的排序就完成了
我们晓得链表始终不能断开的，所以merge方法中不能用null来判断是否合并完一条链表
我们把merge方法设计成
void Merge(ListNode beforeHead, ListNode mid, ListNode afterTail)
- beforehead用于确定head1和合并的指针的位置
- mid是链表2的开始head2(头结点），同时也是链表1的结尾哨兵
- afterTail是链表2的结尾哨兵
那如何确定每次合并的3个参数？
- 对每个len的首次合并，beforeHead为链表头部之前的哨兵节点
- mid为beforeHead后面的第len+1个节点
- afterTail为mid后面的第len个节点
- 使用上述参数完成一个区间的合并
- 下一个区间的beforeHead为beforeHead后面的第len*2个节点
- 以上移动均需注意是否达到链表尾部的null
- 若beforeHead为null，本轮合并完成
时间复杂度是O(nlogn)，空间复杂度是O(1)，只使用了几个变量和1层函数调用
//c#的代码
public class Solution {
public ListNode SortList(ListNode head) {
if(head==null||head.next==null) return head;
int n=0;
ListNode dummy = new ListNode();
dummy.next=head;
var cur = head;
while(cur!=null)
{
cur=cur.next;
n++;
}
int len=1;
while(len<n)
{
var beforeHead=dummy;
while(beforeHead!=null)
{
var mid = beforeHead.next;
for(int i=0;i<len;i++)
{
if(mid!=null) mid=mid.next;
else break;
}
var afterTail=mid;
for(int i=0;i<len;i++)
{
if(afterTail!=null) afterTail=afterTail.next;
else break;
}
Merge(beforeHead,mid,afterTail);
for(int i=0;i<len*2;i++)
{
if(beforeHead!=null)
beforeHead=beforeHead.next;
else break;
}
}
len*=2;
}
return dummy.next;
}
void Merge(ListNode beforeHead, ListNode mid, ListNode afterTail)
{
var cur = beforeHead;
var head1 = cur.next;
var head2 = mid;
while(head1!=mid&&head2!=afterTail)
{
if(head1.val<=head2.val)
{
cur.next=head1;
head1=head1.next;
}
else
{
cur.next=head2;
head2=head2.next;
}
cur=cur.next;
}
while(head1!=mid)
{
cur.next=head1;
head1=head1.next;
cur=cur.next;
}
while(head2!=afterTail)
{
cur.next=head2;
head2=head2.next;
cur=cur.next;
}
cur.next=afterTail;
}
}
