/**

  * 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 == nullptr || head->next == nullptr)

             return head;

         ListNode* slow = head;

         ListNode* fast = head;

         ListNode* mid = nullptr;

         while (fast&&fast->next)

         {

             mid = slow;

             slow = slow->next;

             fast = fast->next->next;

         }

         mid->next = nullptr;

         return mergeHelp(sortList(head), sortList(slow));

     }

     ListNode* mergeHelp(ListNode* low, ListNode* high)

     {

         ListNode* head = new ListNode(-);

         ListNode* cur = head;

         while (low&&high)

         {

             if (low->val < high->val)

             {

                 cur->next = low;

                 low = low->next;

             }

             else

             {

                 cur->next = high;

                 high = high->next;

             }

             cur = cur->next;

         }

         cur->next = low ? low : high;

         return head->next;

     }

 };

 /**

  * 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==nullptr)

             return head;

         quickSort(head,nullptr);

         return head;

     }

     void quickSort(ListNode* begin,ListNode* end)

     {

         if(begin!=end)

         {

             ListNode* sep=getSeperator(begin,end);

             quickSort(begin,sep);

             quickSort(sep->next,end);

         }

     }

     ListNode* getSeperator(ListNode* begin,ListNode* end)

     {

         ListNode* first=begin;

         ListNode* second=begin->next;

         int key=begin->val;

         while(second!=end)

         {

             if(second->val<key)

             {

                 first=first->next;

                 swap(first,second);

             }

             second=second->next;

         }

         swap(begin,first);

         return first;

     }

     void swap(ListNode* a,ListNode* b)

     {

         int tmp=a->val;

         a->val=b->val;

         b->val=tmp;

     }

 };