LeetCode 算法：排序链表 c++

原题链接🔗：排序链表
难度：中等⭐️⭐️

题目

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

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 10⁴] 内
• -10⁵ <= Node.val <= 10⁵

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

题解

1. 题解：

LeetCode 上的 “Sort a linked list” 题目要求我们对链表进行排序。这个问题可以通过多种排序算法来解决，但是使用归并排序是最有效的方法，因为链表不适合使用快速排序或堆排序这类需要随机访问数据的算法。以下是使用归并排序对链表进行排序的解题思路：

• 选择排序算法：由于链表的特性，归并排序是一个很好的选择。归并排序在链表上的实现相对简单，因为它不需要随机访问元素，只需要遍历链表。

• 归并排序链表的步骤： 归并排序链表的步骤如下：

  • 分割链表：找到链表的中点，将链表分为两个子链表。
  • 递归排序：对两个子链表递归地进行排序。
  • 合并链表：合并两个已排序的子链表。

• 实现分割链表：使用快慢指针法来找到链表的中点：

  • 初始化两个指针 slow 和 fast，都指向头节点。
  • fast 每次移动两步，slow 每次移动一步。
  • 当 fast到达链表末尾时，slow 将位于中点。

• 实现递归排序 ：递归地对分割后的两个子链表进行排序：

  • 如果子链表为空或只有一个节点，直接返回该子链表。
  • 否则，分割子链表并递归排序。

• 实现合并链表：合并两个有序链表：

  • 创建一个哑节点（dummy node），用于简化边界条件的处理。
  • 使用一个指针 tail 指向哑节点，用于构建合并后的链表。
  • 比较两个链表头部的节点值，将较小的节点添加到合并后的链表中，并将对应的指针向前移动。
  • 重复上述步骤，直到两个链表中的一个为空。
  • 将非空链表的剩余部分直接连接到合并后的链表。

2. 复杂度：时间复杂度O(nlogn)，其中n是链表的长度；空间复杂度O(1)。
3. c++ demo：

#include <iostream>

// 定义链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;

        // 找到链表的中点，准备分割链表
        ListNode* slow = head, * fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 切割链表
        ListNode* second = slow->next;
        slow->next = NULL;

        // 递归排序链表的两半
        ListNode* left = sortList(head);
        ListNode* right = sortList(second);

        // 合并排序后的链表
        return merge(left, right);
    }

private:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        // 合并两个有序链表
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            }
            else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        // 连接剩余部分
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

int main() {
    Solution solution;
    // 创建示例链表 4 -> 1 -> 3 -> 2 -> NULL
    ListNode* head = new ListNode(4);
    head->next = new ListNode(1);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(2);

    // 排序链表
    ListNode* sortedHead = solution.sortList(head);

    // 打印排序后的链表
    for (ListNode* node = sortedHead; node; node = node->next) {
        std::cout << node->val << " -> ";
    }
    std::cout << "NULL" << std::endl;

    // 释放链表内存
    while (sortedHead) {
        ListNode* temp = sortedHead;
        sortedHead = sortedHead->next;
        delete temp;
    }

    return 0;
}

• 输出结果：

1 -> 2 -> 3 -> 4 -> NULL

归并排序

归并排序（Merge Sort）是一种分治算法，用于对数组或列表进行排序。它基于以下两个原则：

• 分解（Divide）：将数组分成两半，直到每个子数组只有一个元素。
• 合并（Conquer）：将有序的子数组合并成更大的有序数组。