TLE in sortlist merge sort c++


  • 2
    C

    Recursive merge sort function and merge function to join sub lists causing TLE

      class Solution {
        public:
            ListNode *sortList(ListNode *head) {
                if(head==NULL||head->next==NULL)
                    return head;
                ListNode * mid=split(head);
                head=sortList(head);
                mid=sortList(mid);
            ListNode* ret=  merge(head,mid);
            return ret;
        
            }
            ListNode* split(ListNode * root){
                ListNode * ret=root->next;
                ListNode * temp=ret;
                while(root->next=NULL&&root->next->next!=NULL){
                    root->next=root->next->next;
                    temp->next=root->next->next;
                    root=root->next;
                    temp=temp->next;
                }
                root->next=NULL;
        
                return ret;
            }
            ListNode * merge(ListNode * head,ListNode * begin){
                ListNode  temp(-1);
                ListNode * target=&temp;
                while(head!=NULL&&begin!=NULL){
                    if(head->val<=begin->val){
                        target->next=head;
                        head=head->next;
                        target=target->next;
                    }
                    else{
                        target->next=begin;
                        begin=begin->next;
                        target=target->next;
                    }
                }
                if(head!=NULL)
                    target->next=head;
                else
                if(begin!=NULL)
                    target->next=begin;
                return temp.next;
        
            }
        
        };

  • 1
    V

    Run time error Time Limit Exceeded is due to an infinite loop caused by a wrong boolean condition inside the first while loop, it must be while(root->next!=NULL&&root->next->next!=NULL) but inspite of it while(root->next=NULL&&root->next->next!=NULL) is typed. Update the code with this change at line 16.

      class Solution {
        public:
            ListNode *sortList(ListNode *head) {
                if(head==NULL||head->next==NULL)
                    return head;
                ListNode * mid=split(head);
                head=sortList(head);
                mid=sortList(mid);
            ListNode* ret=  merge(head,mid);
            return ret;
    
            }
            ListNode* split(ListNode * root){
                ListNode * ret=root->next;
                ListNode * temp=ret;
                while(root->next!=NULL&&root->next->next!=NULL){
                    root->next=root->next->next;
                    temp->next=root->next->next;
                    root=root->next;
                    temp=temp->next;
                }
                root->next=NULL;
    
                return ret;
            }
            ListNode * merge(ListNode * head,ListNode * begin){
                ListNode  temp(-1);
                ListNode * target=&temp;
                while(head!=NULL&&begin!=NULL){
                    if(head->val<=begin->val){
                        target->next=head;
                        head=head->next;
                        target=target->next;
                    }
                    else{
                        target->next=begin;
                        begin=begin->next;
                        target=target->next;
                    }
                }
                if(head!=NULL)
                    target->next=head;
                else
                if(begin!=NULL)
                    target->next=begin;
                return temp.next;
    
            }
    
        };

  • 6
    T

    I have a simple solution, may be simplest. see below:

    ListNode * sortList(ListNode *head) {
    	if (!head || !head->next) return head;
    
    	ListNode *mid = head, *temp = head->next;
    	while (temp && temp->next) {
    		mid = mid->next;
    		temp = temp->next->next;
    	}
    
    	temp = mid->next; 
    	mid->next = NULL;
    	ListNode *list2 = sortList(temp);
    	ListNode *list1 = sortList(head);
    
    	ListNode **curr = &list1;
    	while (list2 && *curr) {
    		ListNode *entry = *curr;
    		if (list2->val < entry->val) {
    			*curr = list2;
    			list2 = entry;
    		}   
    		curr = &(*curr)->next;
    	}
    	if (list2) *curr = list2;
    
    	return list1;
    }
    

    Firstly, find the middle element and split the link list. Then merge two sorted list, which called list1 and list2.Instead of merge list1 and list2 to a new list, I choose insert every element in list2 to list1. curr is the pointer to last merged element's NEXT pointer.


Log in to reply
 

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