问题描述
给定一个节点数为n的无序单链表，对其按升序排序。
数据范围：0<n≤1000000<n≤100000，保证节点权值在[−109,109][−109,109]之内。
要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
示例1
输入：
[1,3,2,4,5]
返回值：
{1,2,3,4,5}
示例2
输入：
[-1,0,-2]
返回值：
{-2,-1,0}
解题思路
首先，Merge 函数用于合并两个已排序的链表，采用逐个节点比较的方式，将较小的节点接到结果链表中，最终返回合并后的链表头。sortInList 函数通过快慢指针拆分链表，将链表分成两部分，递归地对每部分进行排序。拆分的过程是：慢指针 left 指向链表的头节点，快指针 right 和 mid 找到链表的中点，将链表分成两半，然后对每半部分递归排序，最后通过 Merge 合并两个有序链表。
代码实现
ListNode* Merge(ListNode* head1, ListNode* head2){if(head1 == nullptr) return head2;if(head2 == nullptr) return head1;auto ret = new ListNode(-1);auto head = ret;while (head1 && head2) {if (head1->val < head2->val) {ret->next = head1;head1 = head1->next;}else {ret->next = head2;head2 = head2->next;}ret = ret->next;}if (head1) {ret->next = head1;}if (head2) {ret->next = head2;}return head->next;} ListNode* sortInList(ListNode* head) {// write code hereif (head == nullptr || head->next == nullptr){return head;}ListNode* left = head, *mid = head->next, *right = head->next;while (right && right->next) {left = left->next;mid = mid->next;right = right->next->next;}left->next = nullptr;return Merge(sortInList(head), sortInList(mid));}代码解析
1. 归并排序
如果链表为空或只有一个节点，直接返回链表；通过快慢指针将链表拆分成两部分，递归地对每部分进行排序，然后使用 Merge 合并排序后的子链表，最终返回排序后的链表。
ListNode* sortInList(ListNode* head) {// write code hereif (head == nullptr || head->next == nullptr){return head;}ListNode* left = head, *mid = head->next, *right = head->next;while (right && right->next) {left = left->next;mid = mid->next;right = right->next->next;}left->next = nullptr;return Merge(sortInList(head), sortInList(mid));}2. 合并两个已排序的链表
如果其中一个链表为空，直接返回另一个链表；否则，创建虚拟头节点 ret，逐个比较两个链表的节点，将较小的节点连接到结果链表。最后将剩余的部分连接到结果链表，返回合并后的链表。
ListNode* Merge(ListNode* head1, ListNode* head2){if(head1 == nullptr) return head2;if(head2 == nullptr) return head1;auto ret = new ListNode(-1);auto head = ret;while (head1 && head2) {if (head1->val < head2->val) {ret->next = head1;head1 = head1->next;}else {ret->next = head2;head2 = head2->next;}ret = ret->next;}if (head1) {ret->next = head1;}if (head2) {ret->next = head2;}return head->next;} 总结
本文介绍了如何使用归并排序对链表进行排序。首先通过 Merge 函数合并两个有序链表，再通过 sortInList 函数递归地拆分链表并排序。归并排序的优势在于其稳定性和 O(nlogn)O(n \log n) 的时间复杂度，尤其适合链表结构的排序，因为它不需要额外的数组空间。通过快慢指针的拆分和递归合并，最终实现了一个高效的链表排序算法。