题目：
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
解题思路：
可达到O(nlogn)的排序我们知道有三种，堆排、快排、二路归并。 这里由于是链表，堆排和归并都不太容易操作。所以这里我们用二路归并算法。
二路归并有递归的和非递归的，这里单链表，用非递归较为简单。因为递归要比较两个区间的大小，这里需要用到双指针。
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head == NULL)
return NULL;
ListNode *p = head;
int len = ;
while(p) {
len++;
p = p->next;
} ListNode *temp = new ListNode();
temp->next = head; int interval;
for(interval = ; interval <= len; interval *= ) { //从下往上归并 ListNode *pre = temp;
ListNode *first = temp->next;
ListNode *second = temp->next; while(first && second) {
int i = ;
while(i < interval && second) {
second = second->next;
i++;
}
int fvisit = ;
int svisit = ;
while(fvisit < interval && svisit < interval && first && second) {
if(first->val < second->val) { //前指针较小，则把前指针装入放在前头
pre->next = first;
pre = first;
first = first->next;
fvisit++;
}
else {
pre->next = second;
pre = second;
second = second->next;
svisit++;
}
}
while(fvisit < interval && first) {//剩下的较大的就依次接上就好
pre->next = first;
pre = first;
first = first->next;
fvisit++;
}
while(svisit < interval && second) {
pre->next = second;
pre = second;
second = second->next;
svisit++;
}
pre->next = second; //往后继续直到第一次排序结束
first = second;
}
}
ListNode *ans = temp->next;
delete temp;
return ans;
}
};