First I implemented it by QuickSort, but got a TLE:
class Solution { public: struct Pair { Pair(ListNode *pS, ListNode *pE) : pStart(pS), pEnd(pE) {} ListNode *pStart; ListNode *pEnd; }; void sort(ListNode *pStart, ListNode *pEnd) { if(!pStart) return; if(pStart == pEnd) return; queue<Pair> q; q.push(Pair(pStart, pEnd)); while(!q.empty()) { Pair &in = q.front(); if(in.pStart == in.pEnd) { q.pop(); continue; } // Pivot ListNode *pMid = in.pStart; int mid = in.pStart->val; // Iterate ListNode *p = in.pStart->next; while(p != in.pEnd) { if(p->val <= mid) { int tmp = pMid -> val; pMid -> val = p->val; p->val = tmp; pMid = pMid->next; } p = p->next; } // q.push(Pair(in.pStart, pMid)); if(in.pStart != pMid) q.push(Pair(pMid, in.pEnd)); else q.push(Pair(pMid->next, in.pEnd)); q.pop(); } } ListNode *sortList(ListNode *head) { if(!head || head->next == NULL) return head; sort(head, NULL); return head; } };
And Merge Sort works:
class Solution { public: struct Pair { Pair(ListNode *pS, ListNode *pE) : pStart(pS), pEnd(pE) {} ListNode *pStart; ListNode *pEnd; }; ListNode *merge(ListNode *p0, int cnt0, ListNode *p1, int cnt1) { if(!p0 && !p1) return NULL; if(p0 && !p1) return p0; if(!p0 && p1) return p1; ListNode *pHead = new ListNode(std::numeric_limits<int>::min()); ListNode *pTgt = pHead; while(cnt0 && cnt1) { if(p0->val <= p1->val) { ListNode *pNew = new ListNode(p0->val); pTgt->next = pNew; pTgt = pTgt->next; p0 = p0->next; cnt0--; } else { ListNode *pNew = new ListNode(p1->val); pTgt->next = pNew; pTgt = pTgt->next; p1 = p1->next; cnt1--; } } if(cnt0) { while(cnt0) { ListNode *pNew = new ListNode(p0->val); pTgt->next = pNew; pTgt = pTgt->next; p0 = p0->next; cnt0--; } } if(cnt1) { while(cnt1) { ListNode *pNew = new ListNode(p1->val); pTgt->next = pNew; pTgt = pTgt->next; p1 = p1->next; cnt1--; } } pTgt = pHead->next; delete pHead; return pTgt; } ListNode *sort(ListNode *pStart, int cnt) { if(!pStart || cnt == 1) return pStart; int cnt0 = cnt / 2; int cnt1 = cnt - cnt / 2; // Find half ListNode *p = pStart; int tmp = cnt0; while(tmp--) p = p->next; // ListNode *pl = sort(pStart, cnt0); ListNode *pr = sort(p, cnt1); return merge(pl, cnt0, pr, cnt1); } ListNode *sortList(ListNode *head) { if(!head || head->next == NULL) return head; // Get count int cnt = 0; ListNode *p = head; while(cnt++, p) p = p->next; cnt --; // Go ListNode *pret = sort(head, cnt); return pret; } };
In the quicksort implementation, in each iteration, each item will be visited so there are a lot of list node visit. MergeSort is more straightforward and faster.
LeetCode "Sort List",布布扣,bubuko.com
原文：http://www.cnblogs.com/tonix/p/3886103.html
