/**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 class Solution {

 public:

     ListNode *mergeList(ListNode *h1,ListNode *h2)

     {

        ListNode *head=new ListNode();

        ListNode *cur=head;

        while(h1!=NULL&&h2!=NULL)

        {

            if(h1->val>h2->val)

            {

                cur->next=h2;

                h2=h2->next;

            }

            else

            {

                cur->next=h1;

                h1=h1->next;

            }

            cur=cur->next;

        }

        cur->next=h1==NULL?h2:h1;

        cur=head;

        head=head->next;

        delete cur;

        return head;

     }

     ListNode *sortList(ListNode *head) {

         if(head==NULL||head->next==NULL) return head;

         ListNode *slow,*fast;

         slow=fast=head;

         while(fast->next!=NULL&&fast->next->next!=NULL)

         {

             fast=fast->next->next;

             slow=slow->next;

         }

         ListNode *mid=slow->next;

         slow->next=NULL;

         ListNode *h1=sortList(head);

         ListNode *h2=sortList(mid);

         return mergeList(h1,h2);

     }

 };