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==NULL||head->next==NULL) return head; deque nodeVec; ListNode *root = new ListNode(-1); while(head){ nodeVec.push_back(head); head = head->next; } buildHeap(nodeVec); int size = nodeVec.size()-1; head= extractMin(nodeVec,size); root->next = head; while(size>-1){ head->next = extractMin(nodeVec,size); head = head->next; } head->next=NULL; head = root->next; delete root; return head; } ListNode* extractMin(deque &nodeVec,int &size){ ListNode *minNode = nodeVec[0]; int index = 0; exchange(nodeVec,index,size); --size; MIN_Heapity(nodeVec,index,size); return minNode; } void buildHeap(deque &nodeVec){ int size = nodeVec.size()-1; for(int i = size/2; i>=0; --i){ MIN_Heapity(nodeVec,i,size); } } void MIN_Heapity(deque &nodeVec, int &p,int &size){ if(size<=0) return; int min,index; index = p; min = nodeVec[p]->val; if(2*p+2<=size && min>nodeVec[2*p+2]->val) { min = nodeVec[2*p+2]->val; index = 2*p+2; } if(2*p+1<=size && min>nodeVec[2*p+1]->val){ min = nodeVec[2*p+1]->val; index = 2*p+1; } if(index!=p){ exchange(nodeVec,index,p); MIN_Heapity(nodeVec,index,size); } } void exchange(deque &nodeVec, int &i,int &j){ ListNode* tmp = nodeVec[i]; nodeVec[i] = nodeVec[j]; nodeVec[j] = tmp; }}; TIPS:
用堆排序来做。
本来用快排来做，但最坏情况为O(N ^2)，即使采用随机快排，时间代价也不稳定，尤其对于有大量重复的例子，据说可以去重来处理
如果用归并排序，开全局数组N，我发现上面的写法也用了一个N vector的空间。。再改改