题解 | #单链表的排序#

关键在于归并排序的实用：

归并排序（Merge Sort）是一种分治法的经典应用，它通过将数组分成若干小部分，分别排序后再合并，最终得到一个有序的数组。这个算法的核心思想是“分而治之”，即将问题分解成更小的子问题，解决这些子问题后，再合并得到最终答案。

归并排序的步骤：

1. 分割（Divide）：将数组从中间位置不断地分成两部分，直到每部分只有一个元素为止。例如，给定一个长度为8的数组，我们会先将其分为两个长度为4的数组，然后再将这两个数组继续二分，直到每个子数组只有一个元素。
2. 合并（Conquer）：分割完成后，进入合并阶段。合并时，每次将两个有序的子数组合并成一个更大的有序数组。合并时通过比较两个数组的首元素，依次将较小的元素放入新数组中，直到所有元素合并完成。
3. 递归回归（Combine）：当最底层的子数组合并成更大的有序数组后，递归向上，逐步合并，直到最后生成一个有序的完整数组。

图文解释：

分割阶段：

假设我们有一个数组 [8, 3, 6, 2, 9, 1, 7, 4]。归并排序会首先将其分割成多个小数组：

[8, 3, 6, 2, 9, 1, 7, 4] 
  =>  [8, 3, 6, 2]    [9, 1, 7, 4]
  =>  [8, 3] [6, 2]   [9, 1] [7, 4]
  =>  [8] [3] [6] [2] [9] [1] [7] [4]

合并阶段：

接着从最小的子数组开始，两两合并：

[8] [3] => [3, 8]  [6] [2] => [2, 6]
[9] [1] => [1, 9]  [7] [4] => [4, 7]

接着合并：
[3, 8] [2, 6] => [2, 3, 6, 8]
[1, 9] [4, 7] => [1, 4, 7, 9]

最终合并：
[2, 3, 6, 8] [1, 4, 7, 9] => [1, 2, 3, 4, 6, 7, 8, 9]

最终排序后的数组为 [1, 2, 3, 4, 6, 7, 8, 9]。

归并排序的特点：

1. 时间复杂度：归并排序的时间复杂度为 O(n log n)，即使在最坏情况下也能保持这个效率。
2. 空间复杂度：由于在排序过程中需要额外的空间来存储中间结果，空间复杂度为 O(n)。
3. 稳定性：归并排序是稳定的，即相同元素的相对顺序不会改变。

通过图示和上述步骤可以看出，归并排序的关键在于将数组分成小部分进行排序后再合并，而每次合并都是在有序的基础上进行，因此最终能得到一个有序数组。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        // 链表为空或只有一个节点，直接返回
        if (head == null || head.next == null) {
            return head;
        }
        // 使用归并排序
        // 先把链表分割成两部分，可以借助fast、slow 指针
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;  // 记录 slow 前面的节点，用来分割链表

        while (fast != null && fast.next != null) {
            prev = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        // 分割链表，前半部分为 head，后半部分为 slow
        if (prev != null)
            prev.next = null;  // 断开前后部分

        // 切割成最小颗粒度后合并
        ListNode _left = sortInList(head);
        ListNode _right = sortInList(slow);

        return merge(_left, _right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        }
        ListNode pHead = new ListNode(0);
        ListNode dummy = pHead;
        while (left != null || right != null) {
            if (left == null) {
                pHead.next = right;
                break;
            } else if (right == null) {
                pHead.next = left;
                break;
            } else {
                if (left.val < right.val) {
                    pHead.next = left;
                    left = left.next;
                    // pHead = left; // 要在主链上移动
                } else {
                    pHead.next = right;
                    right = right.next;
                    // pHead = right; // 要在主链上移动
                }
                pHead = pHead.next; // 主链移动
            }
        }
        return dummy.next;
    }
}