148-排序链表

LeetCode 148. Sort List

LeetCode-148

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

归并排序模板

tmp数组作为参数传递可以减少在函数中的多次创建，减少空间复杂度

void merge(vector<int>& nums, int l, int mid, int r, vector<int>& tmp) {
    int cnt = l;    // 辅助数组的指针
    int i = l, j = mid + 1; // 左边和右边数组的指针
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) {   // 这里要小于等于
            tmp[cnt++] = nums[i++];
        }
        else {
            tmp[cnt++] = nums[j++];
        }
    }
    while (i <= mid) tmp[cnt++] = nums[i++];
    while (j <= r) tmp[cnt++] = nums[j++];
    for (int k = l; k <= r; k++) {
        nums[k] = tmp[k];   // 把tmp中保存的有序数值保存到nums中
    }
}

void mergeSort(vector<int>& nums, int l, int r, vector<int>& tmp) {
    if (l == r) return;     // 只有一个元素，不需要排序，直接返回
    int mid = l + (r - l) / 2;  // 计算中间，防止溢出
    mergeSort(nums, l, mid, tmp);       // 递归处理左半区间
    mergeSort(nums, mid + 1, r, tmp);   // 递归处理右半区间
    merge(nums, l, mid, r, tmp);    // 合并左右区间
}

int main(int argc, char const *argv[])
{
    vector<int> nums = {4, 1, 3, 2, 5};
    vector<int> tmp(nums.size());
    mergeSort(nums, 0, nums.size() - 1, tmp);
    return 0;
}
1 2 3 4 5

method: 归并排序

把链表从中间位置断开，就像归并排序的mid一样
分成两串之后，就转化成合并排序链表，直接用21-合并两个排序的链表

ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode *dummy = new ListNode(0);
    ListNode *head = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            head->next = l1;
            l1 = l1->next;
        }
        else {
            head->next = l2;
            l2 = l2->next;
        }
        head = head->next;
    }
    if (l1) head->next = l1;    // 链表用if就可以了
    if (l2) head->next = l2;
    return dummy->next;
}
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;  // 至少要有1个节点
    ListNode *fast = head;
    ListNode *slow = head;
    ListNode *pre = nullptr;    // slow的前一个节点，用来断开链表
    while (fast && fast->next) {
        pre = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    pre->next = nullptr;    // 把链表从中间断开
    ListNode *l1 = sortList(head);  // 前半串
    ListNode *l2 = sortList(slow);  // 后半串
    return merge(l1, l2);
}