1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *sortList( ListNode *head )12     {13         vector<int> vec;14         ListNode *p = head;15         while( p != NULL )16         {17             vec.push_back( p->val );18             p = p->next;19         }20         21         vector<int> tmp( vec.size() );22         23         mergeSort( vec, tmp, 0, vec.size() - 1 );24         25         p = head;26         for(vector<int>::iterator it = vec.begin(); it != vec.end(); it++, p = p->next)27             p->val = *it;28             29         return head;30     }31     32     void mergeSort( vector<int> &vec, vector<int> &tmp, int left, int right )33     {34         if( left < right )35         {36             int center = ( left + right ) / 2;37             mergeSort( vec, tmp, left, center );38             mergeSort( vec, tmp, center + 1, right );39             merge( vec, tmp, left, center + 1, right );40         }41     }42     43     void merge( vector<int> &vec, vector<int> &tmp, int leftPos, int rightPos, int rightEnd )44     {45         int leftEnd = rightPos - 1;46         int tmpPos = leftPos;47         int numElements = rightEnd - leftPos + 1;48         49         while(leftPos <= leftEnd && rightPos <= rightEnd)50             if(vec[leftPos] < vec[rightPos])51                 tmp[tmpPos++] = vec[leftPos++];52             else53                 tmp[tmpPos++] = vec[rightPos++];54                 55         while(leftPos <= leftEnd)56             tmp[tmpPos++] = vec[leftPos++];57             58         while(rightPos <= rightEnd)59             tmp[tmpPos++] = vec[rightPos++];60             61         for(int i = 0; i < numElements; i++, rightEnd--)62             vec[rightEnd] = tmp[rightEnd];63     }64 };