Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Have you met this question in a real interview? 

Yes

Example

Given 1-3->2->null, sort it to 1->2->3->null.

大杂烩。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: You should return the head of the sorted linked list, using constant space complexity. */ ListNode *sortList(ListNode *head) { // write your code here if(!head ||!head->next) return head; ListNode *mid=findMiddle(head); ListNode *tmp=mid->next; mid->next=0; ListNode *left=sortList(head); ListNode *right=sortList(tmp); return mergeList(left,right); } ListNode* findMiddle(ListNode* head){ ListNode* slow=head; ListNode* fast=head->next; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; } return slow; } ListNode* mergeList(ListNode* left, ListNode* right){ ListNode dummy(0); ListNode* head= &dummy; while(left && right){ if (left->val<right->val){ head->next=left; left=left->next; } else{ head->next=right; right=right->next; } head=head->next; } while(left){ head->next=left; head=head->next; left=left->next; } while(right){ head->next=right; head=head->next; right=right->next; } return dummy.next; } };