Wednesday, November 19, 2014

[LeetCode] 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.

思路:

这题的关键是如何track一个节点是否已经被copy了。假如我们要copy如下list,用指针p1来扫描每个节点,另一个指针p2建立copy。
______
|           |
|          V
1->2->3

p1扫描1时,p2复制1,以及1->next (2), 1->random (3)。之后p1, p2分别移到各自的2节点。此时我们必须得知道节点3在之前已经被复制了,并且得知道复制节点的地址。
______
|           |
|          V
1->2    3 

所以这里可以使用一个hash table来记录原节点和复制节点的地址对应关系。这样每次要建立当前节点p的next和random前,先在hash table中查找。如果找到,则直接连接;否则建立新节点连上,并把和原节点的对应关系存入hash table中。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(!head) return NULL;
        unordered_map<RandomListNode*, RandomListNode*> ht;
        RandomListNode *p1 = head;
        RandomListNode *p2 = new RandomListNode(head->label);
        ht[head] = p2;
        while(p1) {
            if(p1->next) {
                if(ht.count(p1->next))
                    p2->next = ht[p1->next];
                else {
                    p2->next = new RandomListNode(p1->next->label);
                    ht[p1->next] = p2->next;
                }
            }
            if(p1->random) {
                if(ht.count(p1->random))
                    p2->random = ht[p1->random];
                else {
                    p2->random = new RandomListNode(p1->random->label);
                    ht[p1->random] = p2->random;
                }
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return ht[head];
    }
};

1 comment:

  1. 看leetcode里有一个很牛的方法实现了。Time O(n), Space O(1)

    ReplyDelete