【C++】LeetCode：LCR 077. 排序链表

题干

LCR 077. 排序链表

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

解法：归并排序

/**
 * 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) {}
 * };
 */
class Solution {
public:
   // 找到链表的中间节点
    ListNode* findMid(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 合并两个有序链表
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode *current = &dummy;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                current->next = l1;
                l1 = l1->next;
            } else {
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }
        current->next = (l1 != nullptr) ? l1 : l2;
        return dummy.next;
    }

    // 归并排序主函数
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // 找到中间节点并断开连接
        ListNode* mid = findMid(head);
        ListNode* rightHead = mid->next;
        mid->next = nullptr;

        // 对左右两部分分别排序
        ListNode* leftSorted = sortList(head);
        ListNode* rightSorted = sortList(rightHead);

        // 合并两个有序链表
        return merge(leftSorted, rightSorted);
    }
};

解析：

归并排序链表算法要点及易错点

算法要点

1. 找到中间节点：

   • 使用快慢指针法找到链表的中间节点。快指针 fast 每次移动两步，慢指针 slow 每次移动一步。当快指针到达链表末尾时，慢指针恰好位于中间节点。
   • 循环条件应为 while (fast->next != nullptr && fast->next->next != nullptr)，以确保快指针不会访问空指针。

2. 断开链表：

   • 找到中间节点后，将中间节点的 next 指针设为 nullptr，从而将链表分成两部分。

3. 递归排序：

   • 对左右两部分分别递归调用 SortList 函数进行排序。

4. 合并两个有序链表：

   • 使用一个虚拟头节点 dummy 来简化合并操作。
   • 遍历两个链表，将较小的节点连接到结果链表中。
   • 最后将剩余的节点连接到结果链表中。

易错点

1. 循环条件：

   • 在 findMid 函数中，确保循环条件为 while (fast->next != nullptr && fast->next->next != nullptr)，以避免访问空指针。

2. 断开链表：

   • 在找到中间节点后，一定要将中间节点的 next 指针设为 nullptr，否则递归调用时会形成环或导致无限递归。

3. 递归终止条件：

   • 确保递归终止条件正确：if (head == nullptr || head->next == nullptr)。如果链表为空或只有一个节点，直接返回。

4. 合并逻辑：

   • 在 merge 函数中，确保遍历两个链表时不会遗漏任何节点。
   • 最后将剩余的节点连接到结果链表中。

复杂度分析：

时间复杂度

1. 找到中间节点（findMid）：

   • 使用快慢指针法找到中间节点的时间复杂度是 O(n)O(n)，其中 nn 是链表的长度。
   • 快指针每次移动两步，慢指针每次移动一步，因此快指针遍历整个链表时，慢指针恰好遍历一半。

2. 递归排序（SortList）：

   • 归并排序的时间复杂度是 O(nlog⁡n)O(nlogn)。
   • 每次递归调用 SortList 将链表分成两半，递归深度为 O(log⁡n)O(logn)。
   • 每一层递归中，合并两个有序链表的时间复杂度是 O(n)O(n)。

3. 合并两个有序链表（merge）：

   • 合并两个有序链表的时间复杂度是 O(n)O(n)，其中 nn 是两个链表的总长度。

综上所述，归并排序链表的整体时间复杂度是 O(nlog⁡n)O(nlogn)。

空间复杂度

1. 递归调用栈：

   • 归并排序是一个递归算法，递归调用栈的空间复杂度是 O(log⁡n)O(logn)，其中 nn 是链表的长度。
   • 每次递归调用 SortList 将链表分成两半，递归深度为 O(log⁡n)O(logn)。

2. 辅助空间：

   • 合并两个有序链表时，使用了一个虚拟头节点 dummy，占用常数级别的空间 O(1)O(1)。

综上所述，归并排序链表的整体空间复杂度是 O(log⁡n)O(logn)。

总结

• 时间复杂度：O(nlog⁡n)O(nlogn)
• 空间复杂度：O(log⁡n)O(logn)