LeetCode 148. 排序链表：归并排序的链表应用

LeetCode 148. 排序链表：归并排序的链表应用

引用

CSDN

1.

https://blog.csdn.net/qq_51350957/article/details/139375004

本文将详细介绍LeetCode第148题"排序链表"的解题思路和代码实现。通过归并排序算法，我们可以以O(nlogn)的时间复杂度和常数级的空间复杂度对链表进行排序。

题目描述

给你链表的头结点 head，请将其按升序排列并返回排序后的链表。

示例

输入：head = [4,2,1,3]
输出：[1,2,3,4]

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]

你可以在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

算法核心思想

算法核心思想是归并排序（Merge Sort）。归并排序是一种分治算法，它将问题分解成更小的子问题来解决，然后逐步合并子问题的解以得到原问题的解。对于链表排序，归并排序的步骤如下：

1. 分解（Divide）：如果链表不为空，将其分成两半。这是通过使用快慢指针实现的，快指针每次移动两个节点，慢指针每次移动一个节点，当快指针到达链表末尾时，慢指针将位于链表的中间位置。

2. 解决（Conquer）：递归地对链表的两半分别进行排序。由于链表是线性结构，这一步实际上是在递归地调用sortList函数，直到链表的长度为1或0，这时链表自然是有序的。

3. 合并（Combine）：将两个有序的链表合并为一个有序链表。这是通过merge函数实现的，它使用两个指针分别遍历两个链表，比较节点的值，将较小的节点依次添加到新链表中，直到两个链表中的一个被完全遍历。然后将另一个链表的剩余部分直接连接到新链表的末尾。

代码实现

递归排序函数

sortList(ListNode* head, ListNode* tail) 函数是实际执行排序的递归函数。

• 如果 head 是 nullptr（空链表），则直接返回 nullptr。
• 如果 head->next 等于 tail，说明只有一个节点，将 head->next 设置为 nullptr 并返回 head。

寻找中间节点

使用快慢指针法（fast 和 slow）找到链表的中间节点。

• slow 每次移动一个节点，而 fast 每次移动两个节点。
• 当 fast 到达 tail 或链表末尾时，slow 将指向中间节点。

递归拆分链表

找到中间节点后，mid 被设置为 slow。

• 递归调用 sortList 函数，分别对 head 到 mid（不包括 mid）和 mid 到 tail 的链表进行排序。

合并排序的链表

递归结束后，使用 merge 函数将两个已排序的子链表合并。

合并函数

merge(ListNode* head1, ListNode* head2) 函数负责合并两个有序链表。

• 创建一个哑节点 dummyHead 作为合并后链表的起点。
• 使用两个指针 temp1 和 temp2 分别遍历两个输入链表。
• 比较 temp1 和 temp2 的值，将较小的节点链接到 dummyHead 的后面，并移动相应的指针。
• 重复这个过程，直到其中一个链表遍历完成。
• 将未遍历完的链表的剩余部分链接到合并后的链表后面。

返回结果

merge 函数返回合并后链表的头节点，即 dummyHead->next。

完整代码

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }
    ListNode* sortList(ListNode* head, ListNode* tail) {
        if (head == nullptr) {
            return head;
        }
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        }
        ListNode* slow = head, *fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) {
                fast = fast->next;
            }
        }
        ListNode* mid = slow;
        return merge(sortList(head, mid), sortList(mid, tail));//一直递归到链表长度为1或0
    }
    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};

注意： 这段代码中的 tail 指针不是指向链表中的最后一个节点，而是指向最后一个节点的下一个节点。这就解释了为什么：

if (head->next == tail) {
    head->next = nullptr;
    return head;
}