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 *merge(ListNode *left,ListNode *right){    ListNode *newl=new ListNode(0);    ListNode *p=newl;    while(left&&right)    {        if(left->val<=right->val)        {           p->next=left;           left=left->next;        }        else        {            p->next=right;            right=right->next;        }        p=p->next;    }    if(left)p->next=left;    if(right)p->next=right;    return newl->next;}ListNode *mergeSort(ListNode *head){    if(head==NULL||head->next==NULL)return head;    ListNode *slow=head;    ListNode *fast=head;    ListNode *pre=NULL;    while(fast&&fast->next)    {        fast=fast->next->next;        pre=slow;        slow=slow->next;    }    pre->next=NULL;    ListNode *left=mergeSort(head);    ListNode *right=mergeSort(slow);    return merge(left,right);}    ListNode *sortList(ListNode *head) {        if(head==NULL||head->next==NULL)return head;        return mergeSort(head);    }};