⭐算法OJ⭐链表排序【归并排序】（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);
}

复杂度

• 时间复杂度：$O(nlogn)$。
• 空间复杂度：$O(logn)$（递归栈空间）。

总结

通过归并排序，我们可以高效地对链表进行排序。这种方法不仅时间复杂度低，而且空间复杂度也较为优秀，适合处理大规模数据。掌握链表的分割和合并技巧对于解决类似的链表问题非常有帮助。