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

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *getMiddle(ListNode *head)    {        ListNode *slow=head;        ListNode *fast=head;        while(fast->next!=NULL&&fast->next->next!=NULL)        {            slow=slow->next;            fast=fast->next->next;        }        return slow;    }    ListNode *Merge(ListNode *head1,ListNode *head2)    {        ListNode *dummy=new ListNode(-1);        ListNode *cur=dummy;        while(head1!=NULL&&head2!=NULL)        {            if(head1->val<head2->val)            {                cur->next=head1;                head1=head1->next;            }            else            {                cur->next=head2;                head2=head2->next;            }            cur=cur->next;        }        while(head1!=NULL)        {            cur->next=head1;            head1=head1->next;            cur=cur->next;        }        while(head2!=NULL)        {            cur->next=head2;            head2=head2->next;            cur=cur->next;        }        return dummy->next;    }    ListNode *sortList(ListNode *head) {        if(head==NULL||head->next==NULL)            return head;        ListNode *mid=getMiddle(head);        ListNode *pHead2=mid->next;        mid->next=NULL;        return Merge(sortList(head),sortList(pHead2));    }};