# My Solution with recusive method(69ms), Not neat, Hope to get help to improve it;

• ``````class Solution {
public:
ListNode *sortList(ListNode *head) {
if(head == NULL) return head;
int n = GetListLength(head);
MergeList(&head, n);
ListNode *next = head;
for(int i=0; i<n-1; i++) next = next->next;
next->next = NULL;
return head;
}
int GetListLength(ListNode *head) {
int n = 0;
while(head != NULL) {
++n;
head = head->next;
}
return n;
}
void MergeList(ListNode **head, int n) {
ListNode *Secondhead = GetSecondhead((*head), n);
if( n>1 ) {
MergeList(head, (n+1)/2);
MergeList(&Secondhead, n/2);
MergeTwoList(head, &Secondhead, (n+1)/2, n/2);
}
}
ListNode *GetSecondhead(ListNode *head, int n) {
for(int i=0; i<(n+1)/2; i++) head = head->next;
return head;
}
void MergeTwoList(ListNode **head, ListNode **Secondhead, int m, int n) {
int i = 0; int j = 0;
ListNode *h1 = *head; ListNode *h2 = *Secondhead; ListNode *preh1 = *head;
while(i<m && j<n) {
if(h1->val < h2->val) { preh1 = h1; h1 = h1->next; i++; }
else {
ListNode *temp = h2->next;
if(preh1==h1) {
h2->next = preh1;
*head = h2;
} else {
h2->next = h1;
preh1->next = h2;
}
preh1 = h2;
j++; h2 = temp;
}
}
if( j<n ) preh1->next = h2;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.