My not very look cool code, but accept in C


  • 0
    L

    step 1: calculate length n, copy List A to B with out random, and store random's point position in array pos[0~n], if NULL, -1
    step 2: filt random in B. for node a in A, find index which A.random's position, and loop index in B and get point b, so point random to b

    int getRandomPos(struct RandomListNode * random, struct RandomListNode * head)
    {
    if (random == NULL)
    {
    return -1;
    }
    struct RandomListNode * p = head;
    int pos = 0;
    while (p != NULL && p != random)
    {
    pos ++;
    p = p->next;
    }
    return pos;
    }

    struct RandomListNode *copyRandomList(struct RandomListNode *head) {

    int n = 0;
    struct RandomListNode * p = head;
    struct RandomListNode * retList, *pre, *cur = NULL;
    while(p != NULL)
    {
        n ++;
        p = p->next;
    }
        
    if (head == NULL)
        return NULL;
    pre = (struct RandomListNode *)malloc(sizeof(struct RandomListNode));
    pre->label = head->label;
    retList = pre;
    
    int * pos = (int *)malloc(sizeof(int) * n);
    pos[0] = getRandomPos(head->random, head);
    p = head->next;
    int i = 1;
    while(p != NULL)
    {
        cur = (struct RandomListNode *)malloc(sizeof(struct RandomListNode));
        cur->label = p->label;
        pre->next = cur;
        pre = cur;
        pos[i++] = getRandomPos(p->random, head);
        p = p->next;
    }
    pre->next = NULL;
    
    struct RandomListNode * pp = retList;
    for(int i = 0; i < n; i ++)
    {
        int index = pos[i];
        int j = 0;
        struct RandomListNode * p = retList;
        while(j<index)
        {
            p=p->next;
            j++;
        }
        if (index == -1)
        {
            pp->random = NULL;
        }
        else
        {
            pp->random = p;
        }
        pp = pp->next;
    }
    return retList;
    

    }


Log in to reply
 

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