Accepted C solution Rt O(n) Sp O(1)


  • 10
    R
    struct RandomListNode *copyRandomList(struct RandomListNode *head) {
    	if(NULL==head) return head;
    
    	struct RandomListNode *p=head;
    	struct RandomListNode *pt;
    
    	//copy
    	while(NULL!=p){
    		pt=p->next;
    		p->next=malloc(sizeof(struct RandomListNode));
    		p->next->label=p->label;
    		p->next->next=pt;
    		p->next->random=NULL; 
    		p=pt;
    	};
    
    	//fix random pointer
    	p=head;
    	while(NULL!=p){
    		if(NULL!=p->random){
    			p->next->random=p->random->next;
    		}
    		p=p->next->next;
    	};
    
    	//separate
    	struct RandomListNode *copyed_head=NULL;
    	p=head;
    	while(NULL!=p){
    		if(NULL!=copyed_head){
    			pt->next=p->next;
    			pt=pt->next;
    		}else{
    			copyed_head=p->next;
    			pt=copyed_head;
    		}
    		p->next=p->next->next;
    		p=p->next;
    	};
    
    	return copyed_head;
    }
    

    Well, someone already share this idea.

    • step 1:copy each node and append it to the original one;
    • step 2:iterate the new list and fix the random pointers
    • step 3:separate the list.

  • 0
    C

    Nice code.But I can't understand why this Solution space is O(1).

     while(NULL!=p){
        pt=p->next;
        p->next=malloc(sizeof(struct RandomListNode));
        p->next->label=p->label;
        p->next->next=pt;
        p->next->random=NULL; 
        p=pt;
    };
    

    In every loop,you malloc(sizeof(struct RandomListNode));.So you have copy the orig list all,the space should be O(N).


  • 0
    R

    To be precise,Here I referred to Auxiliary Space, that is the extra space or temporary space used by an algorithm


  • 0
    F

    this code is so cool


Log in to reply
 

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