博文中会简要介绍Leetcode P0138题目分析及解题思路。
“Copy List with Random Pointer”这道题和p0133十分相似，本质上也是深度优先搜索，运用递归回溯的思想，这道题的核心在于记忆化，即存储每个已经访问过的结点，将其映射到其克隆副本上。在当前结点已经访问过的情况下，无需重复创建副本，直接用其映射的克隆副本即可完成对环的克隆。
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.
The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
以下是Java的题解代码实现。
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if (head == null)
return null;
return this.copy(head, new HashMap<>());
}
private Node copy(Node curr, Map<Node, Node> old2NewMap) {
Node cloned = new Node(curr.val);
old2NewMap.put(curr, cloned);
if (curr.next != null) {
if (old2NewMap.containsKey(curr.next))
cloned.next = old2NewMap.get(curr.next);
else
cloned.next = this.copy(curr.next, old2NewMap);
}
if (curr.random != null) {
if (old2NewMap.containsKey(curr.random))
cloned.random = old2NewMap.get(curr.random);
else
cloned.random = this.copy(curr.random, old2NewMap);
}
return cloned;
}
}
以下是C++的题解代码实现。
/*
// 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 NULL;
unordered_map<Node*, Node*> old2new;
return this->_Copy(head, old2new);
}
private:
Node* _Copy(Node *curr, unordered_map<Node*, Node*> &old2new) {
Node *cloned = new Node(curr->val);
old2new[curr] = cloned;
if (curr->next) {
if (old2new.count(curr->next) > 0)
cloned->next = old2new[curr->next];
else
cloned->next = this->_Copy(curr->next, old2new);
}
if (curr->random) {
if (old2new.count(curr->random) > 0)
cloned->random = old2new[curr->random];
else
cloned->random = this->_Copy(curr->random, old2new);
}
return cloned;
}
};