题解 | #复杂链表的复制#

 * 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指向的结点；时间复杂度n*n
    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;     
}