c++ O(n) time O(1) space solution, with two separate linked list


  • 0
    S

    instead of inserting new node into the original list, it is possible to create a new list at once in a form of array
    by doing this, the RandomListNode->next field could be used to store information
    my solution takes totally 5 rounds, only beats 82.5%

    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head == NULL) return NULL;
        int size = getSize(head);
        //create a list of RandomListNode as an array
        RandomListNode* nhead = (RandomListNode*)new char[sizeof(RandomListNode)*size];
    
        //store the oldlist->random into newlist->next
        //then use the oldlist_i->random to point to corresponding node in newlist (nhead[i])
        //thus ith random pointer in oldlist could be accessed by oldlist_i->random->next
        RandomListNode* cur = head;
        int i = 0;
        while(cur != NULL) {
            nhead[i].label = cur->label;
            nhead[i].next = cur->random;
            cur->random = &nhead[i];
            cur = cur->next;
            i++;
        }
    
        //set up the random pointer in newlist
        cur = head;
        i = 0;
        while(i < size) {
            if (nhead[i].next != NULL)
                nhead[i].random = nhead[i].next->random;
            else
                nhead[i].random = NULL;
            i++;
        }
        i = 0;
    
    
        //restore the oldlist random pointer
        while(cur != NULL) {
            cur->random = cur->random->next;
            cur = cur->next;
        }
    
        //set up the new list next pointer
        while (i < size -1) {
            nhead[i].next = &nhead[i+1];
            i++;
        }
        nhead[i].next = NULL;
        
        return nhead;
    
    }
    int getSize(RandomListNode *head) {
        int size = 0;
        while (head != NULL) {
            head = head->next;
            size ++;
        }
        return size;
    }

  • 0
    A

    @Stuart_Lee If the caller invokes "delete" on each single node, your chunk allocation will crash immediately.
    I tried the same technique in earlier problems. But, if the caller doesn't really free the nodes (strictly speaking, which would be mem leak), but rather terminates itself, then it is fine, but still not recommended.
    After all, if you can't delete a node, what's the point of using linked list?


Log in to reply
 

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