[without extra memory and 0(n) complexity ]4 ms solution in C :) -->Is there any beter solution less than 4 ms in C ?


  • 0
    S

    struct ListNode* reverseKGroup(struct ListNode* head, int k) {

        if (!head || k==1)
            return head;
    
        struct ListNode *curr 		= head;
        struct ListNode *nextNode 	= NULL;
        struct ListNode *prev 		= NULL;
        struct ListNode *savedstart = NULL;
        struct ListNode *endprev    = NULL;
        int count=0;
        while(curr){
    
        	if(count==0)
        		savedstart=curr;//save the start of K-group sub-LinkedList
        	count++;
    
            //reverse the K-group sub-LinkedList
        	nextNode=curr->next;
        	curr->next=prev;
        	prev=curr;
        	curr=nextNode ;
    
    
            if(count==k)//at k point
            {
            	count=0;//reset the count
    
    
            	if(endprev)//endprev is (n-1) start (saved) of K-group
            		endprev->next=prev;//prev will be the last node of the (n) k-sub-linked List  --->thus (n-1)start---connects--->(n) end
            	else
            		head=prev;//for first k-group LL
    
            	endprev=savedstart;//save savedstart pointer as it will change in next iteration and you willrequire in next iteration
            	savedstart->next=NULL;//savedstart assign to NULL to prevent loop
            }
        }
    
    
    
        if(count!=0){//revrese LL
    
        	if(endprev && curr==NULL)
        		endprev->next=savedstart;//for the case handling in which LL is not multiple of K
    
            //rereverse the remaining nodes which are not the multiple of k
        	curr=prev;
        	prev=NULL;
        		    while(count>0){
    
        		    	nextNode=curr->next;
        		    	curr->next=prev;
    
    
        		    	prev=curr;
        		    	curr=nextNode ;
    
        		     	count--;
        		    }
        		    if(curr==NULL)
        		    	head=prev;
        }
    
        return head;
    

    }


Log in to reply
 

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