题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 (O(n log n)) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例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 * 104]内 -105 <= Node.val <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
思路解析
排序的算法有很多，简单的排序算法有类似LeetCode 147 对链表进行插入排序。这里要求时间复杂度为 (O(nlog n))，需要考虑稍微快一些的排序算法，这里采用归并排序。
归并排序并不复杂，但是与常见的数组排序不同，数组排序可以在 (O(1)) 的时间内找到数组的中点，并进行递归。但是在链表中需要找到中点，无法通过 (O(1)) 的复杂度直接查询得到。
这里采用 快慢指针 的方法来查找链表中点，定义 快指针 和 慢指针，快指针每次移动两格，慢指针每次移动一格，快指针移动至末尾时，慢指针移动至中点。这里可能需要细心一些来保证快慢指针不出错。
代码实现
class Solution {
private:
ListNode* mergeList(ListNode* h1, ListNode* h2) {
ListNode* dhead = new ListNode();
ListNode* p1 = h1;
ListNode* p2 = h2;
ListNode* p = dhead;
while(p1 && p2) {
if(p1->val < p2->val) {
p->next = p1;
p = p1;
p1 = p1->next;
}
else {
p->next = p2;
p = p2;
p2 = p2->next;
}
}
if(p1) p->next = p1;
else if(p2) p->next = p2;
return dhead->next;
}
ListNode* mergeSort(ListNode* head) {
if((!head) || (!head->next)) return head;
ListNode* mid = head;
ListNode* fast = head;
while(fast && fast->next) {
fast = fast->next;
if(!fast->next) break;
fast = fast->next;
mid = mid->next;
}
ListNode* h1 = head;
ListNode* h2 = mid->next;
mid->next = nullptr;
return mergeList(mergeSort(h1), mergeSort(h2));
}
public:
ListNode* sortList(ListNode* head) {
return mergeSort(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) {}
* };
*/