题目描述
对链表进行排序,要求时间复杂度O(nlogn)
解题思路
因题目要求复杂第O(nlogn),故可以考虑归并排序
(1)将待排序数组(链表)取中点并一分为二;
(2)递归地对左半部分进行归并排序
(3)递归地对右半部分进行归并排序
(4)将两部分进行合并(merge),得到结果
关键问题
(1)找出链表中点(快慢指针,快指针一次走两步,慢指针一次走一步,快指针在链表末尾时,满指针刚好来到链表中点)
(2)写出归并排序函数
代码示例
class Solution {
public:
ListNode *sortList(ListNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *p = head;
ListNode *q = head->next;
while (q != NULL && q->next != NULL) {
p = p->next;