题目很短：
在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。
最近几天也在做排序算法的实验，所以看到这道题想刷一下。
从题目的要求我们可以大概的想出几种能达到要求的排序：
- 快速排序
- 归并排序
这里是归并排序的实现：
归并排序的大概思路是：
在待排序列中找到中间元素，将待排序列分成两个待排序列，分别对这两个待排序列递归地调用归并排序，当待排序列中元素只剩一个时，序列显然有序。
现在只需要将两个有序序列合并成一个有序序列。
实现：
class ListNode {
public:
int val;
ListNode* next;
ListNode(int v):val(v),next(nullptr){}
}
ListNode * sortList(ListNode * head) {
// write your code here
if (!head || !head->next) return head;
ListNode *fast,*slow;
fast = slow = head;
while(fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow;
slow = slow->next;
fast->next = nullptr;
fast = sortList(head);
slow = sortList(slow);
return mergeList(fast,slow);
}
ListNode *mergeList(ListNode *l1,ListNode *l2){
if (!l1) return l2;
else if (!l2) return l1;
ListNode* ret = new ListNode(0);
ListNode*p = ret;
while(l1 && l2) {
if (l1->val > l2->val) {
ret->next = l2;
ret = ret->next;
l2 = l2->next;
} else {
ret->next = l1;
ret = ret->next;
l1 = l1->next;
}
}
ret->next = (l1)?l1:l2;
ret = p->next;
delete p;
return ret;
}这里的难点就是找出中间元素，将一个序列分成两个序列，这里的实现是快慢指针来实现的，即：
ListNode *fast,*slow;
fast = slow = head;
while(fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}作者：wuxiaobai24
发表日期：9/19/2017
本文首发地址：链表排序
版权声明：CC BY NC SA 4.0
