剑指 Offer 35. 复杂链表的复制
###方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
unordered_map<Node*, Node*> cachedNode;
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
if(!cachedNode.count(head)) {
Node* headNew = new Node(head->val);
cachedNode[head] = headNew;
headNew->next = copyRandomList(head->next);
headNew->random = copyRandomList(head->random);
}
return cachedNode[head];
}
};
|
unordered_map的key为原结点,value为复制的结点.
headNew->next = copyRandomList(head->next) 先从前向后创建复制结点.
回溯过程 headNew->random = copyRandomList(head->random) 从后向前赋值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
| class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
for (Node* node = head; node != nullptr; node = node->next->next) {
Node* nodeNew = new Node(node->val);
nodeNew->next = node->next;
node->next = nodeNew;
}
for (Node* node = head; node != nullptr; node = node->next->next) {
Node* nodeNew = node->next;
nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
}
Node* headNew = head->next;
for (Node* node = head; node != nullptr; node = node->next) {
Node* nodeNew = node->next;
node->next = node->next->next;
nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
}
return headNew;
}
};
|
