题目描述

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

示例 1:

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

示例 2:

输入: -1->5->3->4->0 输出: -1->0->3->4->5

https://leetcode-cn.com/problems/sort-list/

解法1 – 自顶向下的归并排序

首先，时间复杂度限定O(nlogn)，那么在常见的排序算法中，可选的排序算法只有快排、堆排序和归并排序。因为采用了链表这种数据结构，快排和堆排序需要随机访问，因此归并排序较为合适。此外，题目要求常熟级的空间复杂度，也就是说要求原地排序，我们就不能将链表转化为数组排序后再转化为链表。我们在这里贴出常见的排序算法以及相应的空间/时间复杂度。

归并排序分为自顶向下和自底向上两种实现方式，自顶向下需要使用递归来把待排序的数组拆分成两部分，这个过程持续直到待拆分的元素只剩下一个，这一个元素当然是排序好的了。然后我们逐层返回，将排序好的两部分归并，那么归并后的链表也是有序的。严格地说，自顶向下的归并排序并不是常数级空间复杂度，因为递归过程中消耗了系统栈。

下面以示例1: 4->2->1->3为例，图解自顶向下的归并排序过程。为了将链表分为相等的两部分，我们需要寻找链表的中间节点。在这里我们使用了一个技巧，只需要遍历一遍链表就能找到中间节点。

我们寻找到中间节点，记为mid。我们还需要找到中间节点的前一个节点midPrev，因为我们需要将链表断开形成左右两个独立的链表。如果不断开，在寻找中间节点的过程会形成无限递归！！！

[4->2->1->3]会被拆分成[4->2], [1->3]两部分，而[4->2]又会被拆分成[4]和[2]两部分。当链表只剩下一个元素时，自然就是排好序的。我们再返回到上一层，将排好序的元素归并。[4]与[2]归并后会形成[2->4]的链表，而[1]与[3]归并会形成[1->3]的链表，我们再返回更上一层将[2->4]与[1->3]归并得到最终结果[1->2->3->4]。全部代码如下所示。

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode fast = head;
        ListNode mid = head;
        ListNode midPrev = null; // 中间节点的前一个

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            midPrev = mid;
            mid = mid.next;
        }

        if (midPrev != null) midPrev.next = null; // 将链表拆分为左右两半才能合并

        if (mid == head)
            return head;

        ListNode l = sortList(head); // 将左右两部分排序
        ListNode r = sortList(mid);
        // 将排序好的链表归并
        ListNode newHead = new ListNode(0), p = newHead;

        while (l != null && r != null) {
            if (l.val < r.val) {
                p.next = l;
                l = l.next;
            } else {
                p.next = r;
                r = r.next;
            }
            p = p.next;
        }

        if (l != null)
            p.next = l;
        else
            p.next = r;

        return newHead.next; //返回归并好的头节点
    }
}