[leetcode] Copy List with Random Pointer


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.

tag: hashtable, linked-list

虽然被标记为hard,但代码不长。

问题关键是,在拷贝完next指针后,要根据原来链表中的random的地址,找到新建的链表中对应的node的地址,这里我们用一个hashtable来实现,在拷贝next指针时,将对应关系记录下来。

空间复杂度o(n),时间复杂度o(n)。

/**
 * 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:
    unordered_map<RandomListNode *, RandomListNode *> hashTable;
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode * superHeadOld = new RandomListNode(0);
        RandomListNode * superHeadNew = new RandomListNode(0);
        superHeadOld->next = head;
        RandomListNode * p = superHeadOld;
        RandomListNode * np = superHeadNew;
        while(p->next != NULL){
            np->next = new RandomListNode(p->next->label);
            hashTable[p->next] = np->next;
            p = p->next;
            np = np->next;
        }
        p = head;
        np = superHeadNew->next;
        while(p != NULL){
            if(p->random != NULL){
                np->random = hashTable[p->random];
            }
            p = p->next;
            np = np->next;
        }
        np = superHeadNew->next;
        delete superHeadNew;
        delete superHeadOld;
        return np;
    }
};

Untitled

 

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.