[数据结构与算法]力扣 148. 排序链表

题目来源：https://leetcode.cn/problems/sort-list/

大致题意：
给一个链表，将其升序排序后返回

思路

暴力解法的话，可以直接遍历链表将内容存到数组中，然后对数组排序

但是这样违背了对链表排序的本意

那么非暴力如何解题？

分治

可以考虑分治的解法。

对一整个链表排序无从下手，对只有一个元素的链表呢？显然只有一个元素的链表本身即有序。
那么对于两个元素的链表呢？可以将这两个元素分为两个一个元素的链表，然后将其按照升序合并。
同理，如果对两个升序链表，可以通过合并两个升序链表的方法将其合并为升序。

于是可以将原链表分成单个节点，然后再两两合并成升序链表，再将升序链表合并得到最终结果。可以发现，这个思路即为归并排序的思路

具体的解题方法可以概括为：

1. 对于给定的链表，找到链表的中间节点，将中间节点的 next 指针值更新为 null，即将原链表分割为两个子链表。这里需要注意，如果链表为 null，直接返回 null；如果链表只有一个节点，返回单个节点
2. 对两个子链表进行排序，获取排序后的子链表头结点
3. 对排序后的两个子链表进行升序合并

上述找链表中间节点的方法可以通过快慢指针实现

• 初始时，慢指针指向头结点，快指针指向头结点的下一个节点
• 慢节点每次移动一步，快指针每次移动两步。当快指针为空时，慢指针的位置即为中间节点

具体看代码：

    public ListNode sortList(ListNode head) {
        // 为空直接返回
        if (head == null) {
            return null;
        }
        // 单节点直接返回
        if (head.next == null) {
            return head;
        }
        // 使用快慢指针找中间节点
        ListNode mid = null;    // 标记慢指针的上一个位置
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null) {
            mid = slow;
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                break;
            }
        }
        // 将链表分成两部分
        mid.next = null;
        // 排序两个子链表
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        // 合并两个子链表
        return merge(left, right);
    }

    // 合并两个升序链表
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode res = new ListNode(-100001);
        ListNode node = res;
        while (head1 != null || head2 != null) {
            if (head1 == null) {
                node.next = head2;
                head2 = head2.next;
            } else if (head2 == null) {
                node.next = head1;
                head1 = head1.next;
            } else if (head1.val > head2.val) {
                node.next = head2;
                head2 = head2.next;
            } else {
                node.next = head1;
                head1 = head1.next;
            }
            node = node.next;
        }
        return res.next;
    }