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


  • 0
    P
    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;
        }
    };

Log in to reply
 

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