题目描述
Sort a linked list in O(n log n) time using constant space complexity.
采用归并排序
/**
* 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 || !head->next)
return head;
//快慢指针找中点
ListNode *p1 = head, *p2 = head->next;
while(p2 && p2->next)
{
p1 = p1->next;//慢指针
p2 = p2->next->next; //快指针
}
//p1此时就是中点
ListNode* right = sortList(p1->next);//递归右边中点
p1->next = NULL;
ListNode* left = sortList(head);//递归左边中点
return merge(left, right);
}
ListNode *merge(ListNode *left, ListNode *right) {
//创建临时节点
ListNode temp(0);
ListNode *p = &temp;
while(left && right) {
//较小的置于临时节点后
if(left->val < right->val)
{
p->next = left;
left = left->next;
}
else {
p->next = right;
right = right->next;
}
p = p->next;
}
if (left)
p->next = left;
if (right)
p->next = right;
return temp.next;
}
};
