148.排序链表.md

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// 复习
// 归并排序

// 此题较难，包含以下3个小题的内容。主题思想是先递归下探不断拆分，然后递归返回时不断merge。
// 拆分的过程，用到了middleNode：找到链表中间节点（876. 链表的中间结点）。
// merge的过程，用到了合并两个有序链表（21. 合并两个有序链表）。

// 此解法是 O(n log n) 时间复杂度和常数级空间复杂度。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 1、递归结束条件
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 2、找到链表中间节点并断开链表 & 递归下探
        ListNode* mid_node = middleNode(head);
        ListNode* right_head = mid_node->next;
        mid_node->next = nullptr;

        ListNode* left = sortList(head);
        ListNode* right = sortList(right_head);

        // 3、当前层业务操作（合并有序链表）
        // 递归的又一巧妙之处：在每个当前层，如果当前层破坏了，会在最后merge起来，即“每个当前层都会对自己负责”！
        return mergeTwoList(left, right);
    }

    // 找到链表中间节点（876. 链表的中间结点）
    ListNode* middleNode(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 对于0 1 2 3 4，改函数返回的是mid=1（而不是直觉的2），即left=0 1，right=2 3 4
        // 对于0 1 2 3 4 5，改函数返回的是mid=2，即left=0 1 2，right=3 4 5
        // 这样看起来就合理多了。
        ListNode* slow = head;
        ListNode* fast = head->next->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }

    // 合并两个有序链表（21. 合并两个有序链表）
    ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
        ListNode* dummy_node = new ListNode();
        ListNode* cur = dummy_node;

        // dummy_node配合cur进行逐个node的重连工作，l1、l2进行比较和被连接后位移操作。
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }

        // 谁不为空（后面还有node）就连谁，剩下的一定是升序。
        cur->next = l1 ? l1 : l2;
        return dummy_node->next;
    }
};