题解 | #复杂链表的复制#
复杂链表的复制
http://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
/**
-
struct RandomListNode {
-
int label;
-
struct RandomListNode *next;
-
struct RandomListNode *random;
-
};
-
C语言声明定义全局变量请加上static，防止重复定义
-
C语言声明定义全局变量请加上static，防止重复定义 / /*
-
代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
-
@param pHead RandomListNode类
-
@return RandomListNode类 / struct RandomListNode Clone(struct RandomListNode* pHead ) { // write code here //方法：将链表复制，然后在用数组记录每个random指向的结点；时间复杂度nn struct RandomListNode p1 = pHead; int n =0; struct RandomListNode* p2 = NULL; struct RandomListNode* p =(struct RandomListNode*)malloc(sizeof(struct RandomListNode*)); p2 = p; if(!pHead){ return NULL; } //先复制链表 while(p1){ struct RandomListNode* p3= (struct RandomListNode*)malloc(sizeof(struct RandomListNode*)); p3->random = NULL; p3->next = NULL; p3->label = p1->label; p2->next = p3; p2 = p2->next; p1 = p1->next; n +=1;//从1开始计数；最后输出为一共n个结点； }
p1 = pHead;
struct RandomListNode* p4 = pHead;//p4指向要储存random的当前结点； int tempA = (int)calloc(n+1,sizeof(int)); int j = 1; //将random用数组储存； for(int i = 1; i < n+1;i++){ while(p4->random != p1 && p4->random){ p1 = p1->next; j+=1;//从1开始计数； } if(p4->random){ p1 = pHead; *(tempA+i)= j;//第i个结点的random指向第j个结点；tempA[0]不存值 p4 = p4->next; j = 1;
} else{ *(tempA+i)= 0; p4 = p4->next; }} p2 = p->next; p4 = p->next;//p4指向要进行random赋值的结点； int k = 1; for(int i = 1;i < n+1;i++){ if(*(tempA+i) != 0){ for( k = 1; k < *(tempA+i); k++){ p2 = p2->next; } k = 1; p4->random = p2; p2 = p->next; p4 = p4->next; } else{ p4 = p4->next; }
} free(tempA); return p->next;
}
