Mind palace

some thoughts

0%

138. Copy List with Random Pointer

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

O(n) time O(1) space
1->2->3->null变成1->1’->2->2’->3->3’->null
新节点的random = 老节点的random的next，即将老节点和老节点的random的关系赋给新节点和新节点的random
将新老节点分开即可
分三步：

  1. copy next
  2. redirect random
  3. split

切记2跟3不能混做，因为random可能往回指

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        for (auto p = head; p; p = p->next->next) {
            p->next = new Node(p->val, p->next, nullptr);
        }
        for (auto p = head; p; p = p->next->next) {
            p->next->random = p->random ? p->random->next : nullptr; // 一定要注意判空！！
        }
        Node dummy_head(-1, nullptr, nullptr), *tail = &dummy_head;
        for (auto p = head; p; p = p->next) {
            tail->next = p->next;
            tail = tail->next;
            p->next = tail->next;
        }
        return dummy_head.next;
    }
};
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
/**
 * 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) {
        for (auto p = head; p; p = p->next->next) {
            auto n = new RandomListNode(p->label);
            n->next = p->next;
            p->next = n;
        }
        for (auto p = head; p; p = p->next->next) {
            p->next->random = p->random ? p->random->next : nullptr;
        }
        RandomListNode dummy_head(0), *tail = &dummy_head, *p = head;
        while (p) {
            tail->next = p->next;
            tail = tail->next;
            p->next = tail->next;
            p = tail->next;
        }
        return dummy_head.next;
    }
};
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
/**
 * 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) {
        for (auto curr = head; curr; curr = curr->next) {
            auto node = new RandomListNode(curr->label);
            node->next = curr->next;
            curr->next = node;
            curr = node;
        }

        for (auto curr = head; curr; curr = curr->next->next) {
            if (curr->random) {
                curr->next->random = curr->random->next;
            }
        }

        RandomListNode dummy_head(0);
        dummy_head.next = head;
        for (auto curr = head, succ = &dummy_head; curr; curr = curr->next) {
            succ->next = curr->next;
            succ = succ->next;
            curr->next = succ->next;
        }
        return dummy_head.next;
    }
};

hashmap O(n) time O(n) space 先复制，再连

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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) {
        unordered_map<RandomListNode *, RandomListNode *> m;
        for (auto p = head; p; p = p->next) {
            m[p] = new RandomListNode(p->label);
        }
        for (auto p = head; p; p = p->next) {
            m[p]->next = p->next ? m[p->next] : nullptr;
            m[p]->random = p->random ? m[p->random] : nullptr;
        }
        return head ? m[head] : nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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) {
        unordered_map<RandomListNode *, RandomListNode *> hm;
        for (auto node = head; node; node = node->next) {
            hm[node] = new RandomListNode(node->label);
        }
        for (const auto &p : hm) {
            if (p.first->next) hm[p.first]->next = hm[p.first->next];
            if (p.first->random) hm[p.first]->random = hm[p.first->random];
        }
        return hm[head];
    }
};