链表的归并排序

在对数组进行排序时，归并排序时间复杂度为nlongn，空间复杂度为n；快速排序的时间复杂度是n~nlogn之间，空间复杂度是logn；堆排序的时间复杂度是nlogn，空间复杂度是1.

但是在对链表进行排序时，归并排序可以实现常数的空间复杂度，而且时间复杂度依然是nlogn。

leetcode148题

题目描述：

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

示例 1:输入: 4->2->1->3 输出: 1->2->3->4

示例 2:输入: -1->5->3->4->0 输出: -1->0->3->4->5

解决思路：

1. 要求是nlogn时间复杂度和常数级的空间复杂度，因此应该采用堆排序，快速排序的空间复杂度是logn，归并排序的空间复杂度是n,但是，此处的排序是对链表进行排序，我们在对数组进行排序时，可以在原数组上进行排序，因此空间复杂度可以是常数，但是此处是链表，若直接使用堆排序，而且使用PriorityQueue依然会将数据先复制出来，并占用线性的空间复杂度。
            2. 另外一种方法时采用归并排序的思想，进行归并排序，我们知道归并排序的时间复杂度是nlogn，而由于此处是链表，我们可以实现常数空间复杂度。
            参考：Sort List——经典（链表中的归并排序）https://www.cnblogs.com/qiaozhoulin/p/4585401.html
            归并排序法：在动手之前一直觉得空间复杂度为常量不太可能，因为原来使用归并时，都是 O(N)的，需要复制出相等的空间来进行赋值归并。对于链表，实际上是可以实现常数空间占用的（链表的归并 排序不需要额外的空间）。利用归并的思想，递归地将当前链表分为两段，然后对两段分别进行递归调用排序方法，然后合并（merge），分两段的方法是使用 fast-slow 法，用两个指针，一个每次走两步，一个走一步，直到快的走到了末尾，然后慢的所在位置就是中间位置，这样就分成了两段。merge时，把两段头部节点值比较，用一个 p 指向 较小的，且记录第一个节点，然后两段的头一步一步向后走，p也一直向后走，总是指向较小节点，直至其中一个头为NULL，处理剩下的元素。最后返回记录的头即可。
             主要考察3个知识点
             知识点1：归并排序的整体思想
             知识点2：找到一个链表的中间节点的方法
             知识点3：合并两个已排好序的链表为一个新的有序链表

实现代码：分别是方法一和方法二的代码

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null)
            return null;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        while(head != null){
            pq.offer(head.val);
            head = head.next;
        }
        
        ListNode cur = new ListNode(0);
        ListNode result = cur;
        while(pq.size() != 0){
            cur.val = pq.poll();
            if(pq.size() != 0)
                cur.next = new ListNode(0);
            cur = cur.next;
        }
        
        return result;
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        return head == null ? null : mergeSort(head);
    }

    private ListNode mergeSort(ListNode head) {
        if (head.next == null) {
            return head;
        }

        //fast-slow将链表切成两段
        ListNode p = head, q = head, pre = null;
        while (q != null && q.next != null) {
            pre = p;
            p = p.next;
            q = q.next.next;
        }
        pre.next = null;
        
        //递归调用排序方法，将两段进行排序
        ListNode l = mergeSort(head);
        ListNode r = mergeSort(p);

        //将排序后的两段进行合并（merge）
        return merge(l, r);
    }

    //将两段进行合并的方法
    ListNode merge(ListNode l, ListNode r) {
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l != null && r != null) {
            if (l.val <= r.val) {
                cur.next = l;
                cur = cur.next;
                l = l.next;
            } else {
                cur.next = r;
                cur = cur.next;
                r = r.next;
            }
        }
        if (l != null) {
            cur.next = l;
        }
        if (r != null) {
            cur.next = r;
        }
        return dummyHead.next;
    }
}