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

• ``````struct RandomListNode *copyRandomList(struct RandomListNode *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
while(NULL!=p){
if(NULL!=p->random){
p->next->random=p->random->next;
}
p=p->next->next;
};

//separate
while(NULL!=p){
pt->next=p->next;
pt=pt->next;
}else{
}
p->next=p->next->next;
p=p->next;
};

}
``````

• 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.

• 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).

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

• this code is so cool

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