[NC]70. 单链表的排序

🚩传送门：牛客题目

题目

给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 ：

输入：head = [4,2,1,3] 输出：[1,2,3,4]

解题思路：手动模拟插入

最容易想到的思路
备注：一般链表为了方便操作，都会创建一个 dummyHead 头结点
将未排序列表的每个结点依次取出，然后插入到已排序的列表中使之有序，插入的过程为：
利用 pNode 从新链表的 dummyHead 检查至 Tail ，直至遇到 waitSortNode.val <= pNode.next.val ，便将
waitSortNode 插入至 pNode 后面 。（此时 pNode 指向的结点正好为待插入位置的上一个结点）

复杂度分析

时间复杂度： ，待排序的 n 个结点，每个结点都需要遍历 n 次。

空间复杂度：，没有使用额外空间

我的代码

public class Solution {
    public ListNode sortInList (ListNode head) {
        if(head==null)return head;
        // 创建新的头结点,便于操作
        ListNode dummyHead =new ListNode(Integer.MIN_VALUE);
        while(head!=null){//只要head还有结点
            ListNode waitSortNode=head;
            head=head.next;
            ListNode pNode=dummyHead;
            while(pNode.next!=null&&waitSortNode.val>pNode.next.val){
                pNode=pNode.next;
            }
            waitSortNode.next=pNode.next;
            pNode.next=waitSortNode;
        }
        return dummyHead.next;
    }
}

解题思路：优先队列 -> 小根堆

创建一个小根堆，将每个链表结点放入小根堆中，依次吐出，每次吐出的都是 ListNode.val 值最小的结点，利用 Tail 将吐出的结点依次插入 新链表的尾部 即可实现链表排序。

复杂度分析

时间复杂度： ，优先队列内部结构是堆，堆排序时间复杂度是 。

空间复杂度：，队列内部需要存储 n 个指针变量。

我的代码

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null)return head;
        //1.创建小根堆
        Queue<ListNode>queue=new PriorityQueue<ListNode>((val1, val2)->val1.val-val2.val);
        //2.所有结点入堆
        while(head!=null){
            queue.add(head);
            head=head.next;
        }
        ListNode Head=null;
        Head=queue.poll();
        ListNode Tail=Head;
        //3.依次吐出堆中结点,追加至新链表的尾部
        while(!queue.isEmpty()){
            Tail.next=queue.poll();
            Tail=Tail.next;
        }
        Tail.next=null;
        return Head;
    }
}

解题思路：归并排序

题目要求时间空间复杂度分别为 和 ，根据时间复杂度我们自然想到二分法，从而联想到归并排序

对数组做归并排序的空间复杂度为 ，分别由新开辟数组 和递归函数调用 组成，
而根据链表特性：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间，因此是

通过递归实现链表归并排序，有以下两个环节：
分割 cut 环节： 找到当前链表中点，并从中点将链表断开，分别递归左右两个链表。

• 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。

  找到中点 slow 后，执行 slow.next = null 将链表切断。

• 分别递归左右两个链表，左端点为原链表的 head ，右端点为中心节点 slow 的下一个节点 head2

• cut 递归终止条件： 只有一个节点时，直接返回此节点。

合并 merge 环节： 二路归并，将两个排序链表合并为一个排序链表。

复杂度分析

时间复杂度： ，使用的是归并排序。

空间复杂度：，常数固定空间

我的代码

class Solution {
    public static ListNode sortList(ListNode head) {
        //1.空结点或单结点,直接返回
        if (head == null || head.next == null)
            return head;
        //2.双指针找中点
        ListNode fast = head.next,slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode head1 = head;                //左区间端点:head
        ListNode head2 = slow.next;           //右区间端点:slow.next
        slow.next = null;                     //断开,左区间为[head,slow],右区间为[head2,null)
        ListNode list1 = sortList(head1);      //左区间归并后的有序的新链表list1
        ListNode list2 = sortList(head2);      //右区间归并后的有序的新链表list
        //3.二路归并
        ListNode dummyHead = new ListNode(0); //方便归并的头部结点
        ListNode  pCur= dummyHead;            //二路归并的哨兵指针
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {      //值小的结点添加至新链表
                pCur.next = list1;
                list1 = list1.next;
            } else {
                pCur.next = list2;
                list2 = list2.next;
            }
            pCur = pCur.next;
        }
        pCur.next = list1 != null ? list1 : list2;//将非空一方添加进新链表
        return dummyHead.next;
    }
}

解题思路：归并排序（从底至顶直接合并）

个人认为这个方法太复杂没必要
对于非递归的归并排序，需要使用迭代的方式替换cut环节：
我们知道，cut 环节本质上是通过二分法得到链表最小节点单元，再通过多轮合并得到排序结果。

• 每一轮合并 merge 操作针对的单元都有固定长度 intv，例如：
• 第一轮合并时 intv = 1，即将整个链表切分为多个长度为 1 的单元，并按顺序两两排序合并，合并完成的已排序单元长度为 2。
• 第二轮合并时 intv = 2，即将整个链表切分为多个长度为 2 的单元，并按顺序两两排序合并，合并完成已排序单元长度为 4。
• 以此类推，直到单元长度 intv >= 链表长度，代表已经排序完成。

本质来说就是：使用迭代的方式替换递归切割环节

复杂度分析

时间复杂度： ，使用的是归并排序。

空间复杂度：，常数固定空间

我的代码

class Solution {
    public static ListNode sortList(ListNode head) {
        if (head == null||head.next==null) return head;
        int length = 0;
        ListNode node = head;
        //1.统计链表长度
        while (node != null) {
            length++;
            node = node.next;
        }
        ListNode dummyHead = new ListNode(0, head); //创建有序链表的头结点
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = dummyHead, curr = dummyHead.next;   //prev保存for一次循环中的有序部分
            //2.切割
            while (curr != null) {
                //#1.统计第一个长度为subLength的链表,端点为head1
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                //#2.统计第二个长度为subLength的链表,端点为head2
                ListNode head2 = curr.next;
                curr.next = null;
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode next = null;
                //pre存储已操作部分,cur存储后面未操作部分
                if (curr != null) {
                    next = curr;
                    curr = curr.next;
                    next.next=null;
                }
                //3.合并操作
                ListNode merged = merge(head1, head2);
                //#3.将已合并部分与pre已操作部分连接,pre后移指向已操作部分的最后一个结点,等待接下来的合并部分的到来
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }
            }
        }
        return dummyHead.next;
    }
    public static ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);    //方便归并的头部结点
        ListNode  pCur= dummyHead;                   //二路归并的哨兵指针
        while (list1 != null && list2 != null) {
            //将值小的添加至新链表
            if (list1.val < list2.val) {
                pCur.next = list1;
                list1 = list1.next;
            } else {
                pCur.next = list2;
                list2 = list2.next;
            }
            pCur = pCur.next;
        }
        //将非空一方添加进新链表
        pCur.next = list1 != null ? list1 : list2;
        return dummyHead.next;
    }
}