Cinte's Leetcode Record
0%

剑指 Offer 35. 复杂链表的复制

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

剑指 Offer 35. 复杂链表的复制

参考138. Copy List with Random Pointer

建立新节点和老节点的映射
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
/*
// 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) {
        unordered_map<Node*, Node*> map;
        Node* pre = new Node(0);
        Node* pseudoHead = pre;
        while(head)
        {
            auto node = new Node(head->val);
            pre->next = node;
            map[head] = node;
            pre = node;
            head = head->next;
        }
        for(auto& it : map)
        {
            if(it.first->random)
                it.second->random = map[it.first->random];
            else
                it.second->random = nullptr;
        }
        return pseudoHead->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
35
/*
// 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) {
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        while(cur)
        {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while(cur)
        {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[head];
    }
};
拼+拆
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
/*
// 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;
        auto cur = head;
        while(cur)
        {
            auto next = cur->next;
            cur->next = new Node(cur->val);
            cur->next->next = next;
            cur = next;
        }
        cur = head;
        while(cur)
        {
            if(cur->random)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        cur = head;
        auto newL = head->next;
        auto ret = newL;
        while(newL->next)
        {
            cur->next = cur->next->next;
            newL->next = newL->next->next;
            cur = cur->next;
            newL = newL->next;
        }
        cur->next = nullptr;
        return ret;
    }
};