Cinte's Leetcode Record
0%

138. Copy List with Random Pointer

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

138. Copy List with Random Pointer

hashmap && vector
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        int i = 0;
        auto headTmp = head;
        Node* newHead = new Node(0);
        Node* newHeadTmp = newHead;
        
        unordered_map<Node*, int> map;
        vector<Node*> newMap;
        while(headTmp)
        {
            Node* nodeTmp = new Node(headTmp->val);
            
            newHeadTmp->next = nodeTmp;
            newHeadTmp = newHeadTmp->next;
            
            newMap.push_back(nodeTmp);
            map[headTmp] = i++;
            
            headTmp = headTmp->next;
        }
        headTmp = head;
        
        newHeadTmp = newHead;
        newHead = newHead->next;
        delete newHeadTmp;
        
        i = 0;
        while(headTmp)
        {
            if(headTmp->random)
                newMap[i]->random = newMap[map[headTmp->random]];
            else
                newMap[i]->random = nullptr;
            ++i;
            headTmp = headTmp->next;
        }
        return newHead;
    }
};

T(n) : O(n)
S(n) : O(n)

discussion中O(1) space Complexity 的方法，实际上还是O(n)
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)
            return nullptr;
        Node* headTmp = head;
        while(headTmp)
        {
            Node* node = new Node(headTmp->val);
            auto next = headTmp->next;
            headTmp->next = node;
            node->next = next;
            headTmp = next;
        }
        headTmp = head;
        while(headTmp)
        {
            if(headTmp->random)
                headTmp->next->random = headTmp->random->next;
            headTmp = headTmp->next->next;
        }
        headTmp = head;
        Node* newHead = head->next;
        Node* newHeadTmp = newHead;
        while(newHeadTmp->next)
        {
            headTmp->next = headTmp->next->next;
            headTmp = headTmp->next;
            
            newHeadTmp->next = headTmp->next;
            newHeadTmp = newHeadTmp->next;
        }
        headTmp->next = headTmp->next->next;
        newHeadTmp->next = nullptr;
        return newHead;
    }
};

T(n) : O(n)
S(n) : O(n)