⭐算法OJ⭐链表排序【归并排序】（C++/JavaScript 实现）

文章目录

- 148. Sort List
- 解题思路
- - 归并排序的基本思想
  - 归并排序的步骤
- 实现
- - 实现步骤
  - C++ 实现
  - JavaScript 实现
- 复杂度
- 总结

148. Sort List

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

在这里插入图片描述

解题思路

链表排序问题可以通过多种方法解决，常见的方法是归并排序（Merge Sort）。归并排序（Merge Sort） 是一种基于 分治法（Divide and Conquer）的排序算法。它的核心思想是将一个大问题分解为多个小问题，分别解决后再将结果合并。归并排序的主要特点是稳定、时间复杂度低，并且适合处理大规模数据。

归并排序的基本思想

分（Divide）：
- 将待排序的数组或链表递归地分成两半，直到每个子数组或子链表只包含一个元素（或为空）。
- 单个元素的数组或链表本身就是有序的。
治（Conquer）：
- 将两个 有序的子数组或子链表 合并成一个更大的有序数组或链表。
- 合并过程中，通过比较两个子数组或子链表的元素，按顺序将较小的元素放入结果中。
合（Combine）：
- 重复合并过程，直到所有子数组或子链表合并成一个完整的有序数组或链表。

归并排序的步骤

分割：
- 将数组或链表从中间分成两部分。
- 对每一部分递归地进行分割，直到无法再分。
合并：
- 将两个有序的部分合并成一个有序的整体。
- 合并时，通过比较两个部分的元素，按顺序将较小的元素放入结果中。
- 给定一个链表的头节点 head，要求将其按升序排序，并返回排序后的链表。

实现

实现步骤

分割链表：
- 使用快慢指针法找到链表的中间节点。
- 将链表从中间节点分为两部分。
递归排序：对左右两部分链表分别递归调用 sortList 排序函数。
合并链表：使用 merge 函数将两个有序链表合并为一个有序链表。
虚拟头节点：在合并链表时，使用虚拟头节点简化代码。

C++ 实现

// 链表节点定义
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 合并两个有序链表
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;
}// 归并排序主函数
ListNode* sortList(ListNode* head) {if (!head || !head->next) {return head; // 链表为空或只有一个节点，直接返回}// 使用快慢指针找到链表的中间节点ListNode* slow = head;ListNode* fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}// 分割链表ListNode* mid = slow->next;slow->next = nullptr;// 递归排序左右两部分ListNode* left = sortList(head);ListNode* right = sortList(mid);// 合并两个有序链表return merge(left, right);
}

JavaScript 实现

// 链表节点定义
class ListNode {constructor(val, next = null) {this.val = val;this.next = next;}
}// 合并两个有序链表
function merge(l1, l2) {const dummy = new ListNode(0); // 虚拟头节点let 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;
}// 归并排序主函数
function sortList(head) {if (!head || !head.next) {return head; // 链表为空或只有一个节点，直接返回}// 使用快慢指针找到链表的中间节点let slow = head;let fast = head.next;while (fast && fast.next) {slow = slow.next;fast = fast.next.next;}// 分割链表const mid = slow.next;slow.next = null;// 递归排序左右两部分const left = sortList(head);const right = sortList(mid);// 合并两个有序链表return merge(left, right);
}