An intuitive solution along with a tricky one in C, both well-explained


  • 0

    The intuitive one is quite direct, shallow copy first -> just copy the label part and the next pointer; and along the way we collect the corresponding relations between the original nodes and the new nodes in a dictionary for latter use in random pointer copy.

    Quite simple, right? But just as you can imagine the performance will be pretty bad.

    • space complexity O(n) with the dictionary;
    • time complexity O(n^2) with the random pointer searching part;

    Bang! End of this section!


    struct Mapper
    {
        struct RandomListNode *key;
        struct RandomListNode *value;
    };
    
    struct RandomListNode *nodeMaker(struct RandomListNode *node)
    {
        struct RandomListNode *t = (struct RandomListNode*)malloc(sizeof(struct RandomListNode));
        t->label = node->label;
        t->next = node->next;
        t->random = node->random;
        return t;
    }
    
    //AC - 84ms;
    struct RandomListNode *copyRandomList(struct RandomListNode *head)
    {
        if(!head) return NULL;
        struct RandomListNode *newHead = nodeMaker(head);
        struct RandomListNode *t = newHead;
        struct RandomListNode *p = head;
        struct Mapper *dict = (struct Mapper*)malloc(sizeof(struct Mapper));
        int size = 0;
        while(p) //doing the complete copy but the random will be further handled;
        {
            struct RandomListNode *t0 = nodeMaker(p);
            size++;
            dict = (struct Mapper*)realloc(dict, sizeof(struct Mapper)*size); //mapping for later random pointer;
            dict[size-1].key = p;
            dict[size-1].value = t0;
            t->next = t0;
            p = p->next;
            t = t->next;
        }
        p = newHead->next;
        while(p)
        {
            for(int i = 0; i < size; i++)
            {
                if(!p->random) break;
                if(dict[i].key == p->random)
                {
                    p->random = dict[i].value;
                    break;
                }
            }
            p = p->next;
        }
        return newHead->next;
    }
    

    Another tricky one is going to be bad! ^^ We can just copy the node and place the newly copied node just after the original one and then:

    • what about the random pointer? the random pointer will also point to a node in the original linked list, right? Now the random pointer of the new node, how can we get that? use the node A0 before the new node A1 -> suppose the random pointer of A0 will point to B -> and B0 will be place just after B -> since we place all new nodes right after the original ones so another next will get us there! Huh! All because we just wisely placed the newly copied one after its corresponding original one, right?

    Before we truly end this whole story, we have to split the original and the newly copied -> just another separating the odd (original) and the even (newly copied) nodes in a linked list -> easy one!

    So easy so bad!

    End of the whole Story!

    • space cost O(1) since we just need to record some critic nodes;
    • time cost O(n) just traverse the linked list three times: copy and insert, copy random pointers, split them up to restore the original list;

    //AC - 28ms;
    struct RandomListNode* copyRandomList(struct RandomListNode *head)
    {
        if(!head) return NULL;
        struct RandomListNode *newHead=NULL, *oldNode=head, *newNode=NULL;
        while(oldNode) //copy the node and place the new node just after the original one;
        {
            newNode = (struct RandomListNode*)malloc(sizeof(struct RandomListNode));
            newNode->next = oldNode->next;
            newNode->label = oldNode->label;
            newNode->random = NULL;
            oldNode->next = newNode;
            oldNode = oldNode->next->next;
        }
        oldNode = head;
        while(oldNode) //using the adjacent attribute to find the random pointer;
        {
            if(oldNode->random)
                oldNode->next->random = oldNode->random->next;
            oldNode = oldNode->next->next;
        }
        
        newHead = head->next;
        newNode = head->next;
        oldNode = head;
        while(oldNode) //splitting the two merged list into two independent ones restoring the original list;
        {
            oldNode->next = oldNode->next->next;
            if(oldNode->next == NULL)
            {
                newNode->next = NULL;
                break;
            }
            newNode = newNode->next->next;
            newNode = newNode->next;
            oldNode = oldNode->next;
        }
        return newHead;
    }

Log in to reply
 

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