Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Problem link

Solution

  • the random pointer may point to a node that hasn’t been created yet
  • create the linked list first, and then add random pointers in the second pass using hashtable constant-time lookup
  • need two passes
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // two lookups: ori.cur ->(using pointer) ori.rand -> new.rand
        unordered_map<RandomListNode*, RandomListNode*> h;
        RandomListNode* dummy = new RandomListNode(0);
        RandomListNode* cur = head;
        RandomListNode* new_cur = dummy;
        // linking next pointers
        while (cur){
            new_cur->next = new RandomListNode(cur->label);
            h[cur] = new_cur->next;
            cur = cur->next;
            new_cur = new_cur->next;
        }
        new_cur->next = NULL;
        // linking random pointers
        cur = head;
        new_cur = dummy->next;
        while (cur){
            new_cur->random = cur->random? h[cur->random]:NULL;
            new_cur = new_cur->next;
            cur = cur->next;
        }
        new_cur = dummy->next;
        delete(dummy);
        return new_cur;
    }
};
Advertisements
Copy List with Random Pointer

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s