LeetCode
题目描述
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
【示例 1】
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
【示例 2】
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
【示例 3】
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
【提示】
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。
【难度】
中等
解题
迭代 I
【思路】
我的第一想法是先将整个链表的所有节点复制一遍，然后建立next和random关系。为了能建立关系，将复制的所有节点按照顺序保存，这里我第一想法是保存到vector中。第二遍遍历建立next关系和random关系，建立next关系很简单，通过索引即可。如何建立random关系呢？我需要将新链表与旧链表的节点对应起来，因此我想到了哈希表。对于当前节点，如果其next或random指向的节点不存在，则创建并作记录，同时建立链接关系；如果节点已经建立，则直接指定链接关系。一切迎刃而解，以下是代码，一遍过。
/*
// 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 == nullptr)
return head;
Node *cur_node = head;
map<Node*, int> dict;
vector<Node *>nodes;
int i=0;
while(cur_node){
Node *new_node = new Node(cur_node->val);
nodes.push_back(new_node);
dict[cur_node] = i;
cur_node = cur_node->next;
++i;
}
i=0;
while (head){
if (head->next)
nodes[i]->next = nodes[i+1];
if (head->random)
nodes[i]->random = nodes[dict[head->random]];
head = head->next;
++i;
}
return nodes[0];
}
};
空间复杂度：
需要存储整个链表的vector以及一个map，因此空间复杂度为O(N)。
时间复杂度：
遍历两次链表，时间复杂度O (N)。
迭代 II
在尝试其他方法时，我发现上面方法中，我只需要将将新链表与旧链表的节点对应起来就可以了。以下是修改后的代码：
/*
// 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 == nullptr)
return head;
Node *new_head = new Node(head->val);
Node *cur_node = new_head;
map<Node*, Node*> dict;
dict[head] = new_head;
while(head){
if (head->random && dict[head->random]==nullptr){
Node *new_node = new Node(head->random->val);
dict[head->random] = new_node;
}
if (head->next && dict[head->next]==nullptr){
Node *new_node = new Node(head->next->val);
dict[head->next] = new_node;
}
cur_node->random = dict[head->random];
cur_node->next = dict[head->next];
head = head->next;
cur_node = cur_node->next;
}
return new_head;
}
};
回溯法
考虑到第一种迭代方法，我们要创建整个链表一样的新链表，随后建立对应关系。如果链表只有next分支，不存在random的话，我们可以通过递归来完成链表的深拷贝，即由前到后创建节点，弹出过程建立链接。这里可以使用同样的思想，无非通路由一个变成两个。以下是代码：
/*
// 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:
map<Node*, Node*> dict;
Node* copyRandomList(Node* head) {
if (head == nullptr)
return head;
if (dict[head]==nullptr){
Node *new_head = new Node(head->val);
dict[head] = new_head;
dict[head]->next = copyRandomList(head->next);
dict[head]->random = copyRandomList(head->random);
}
return dict[head];
}
};
迭代 III
这个看了题解才意识到，不得不佩服居然能想到这种方法。迭代部分说过新链表节点之间关系的建立需要依靠新旧链表对应节点的对应关系，所以不管是迭代还是回溯都使用到了哈希表。那能不能不借助哈希表，不使用额外的存储空间呢？可以！问题的本质是不使用额外空间来创建对应关系，那可以在旧链表的基础上，将新链表的节点放在旧链表对应节点的后面一个位置。比如旧链表是{1-2-3-4}结构，我们在旧链表上增加新链表节点之后变成了{1-1’-2-2’-3-3’-4-4’}，以此建立了对应节点的对应关系。我们要做的是：
- 在旧链表节点位置后增加新链表的节点
- 为新链表节点增加random关系
- 为新链表节点增加next关系
注意要先建立random关系，因为建立next关系之后，新链表就脱离旧链表成为一个独立的链表，此时对应关系丢失，将无法继续建立random关系。以下是代码：
/*
// 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 == nullptr)
return head;
Node *cur_node = head;
while (cur_node){
Node *new_node = new Node(cur_node->val);
new_node->next = cur_node->next;
cur_node->next = new_node;
cur_node = new_node->next;
}
cur_node = head;
while (cur_node){
if (cur_node->random)
cur_node->next->random = cur_node->random->next;
cur_node = cur_node->next->next;
}
Node *new_head = head->next;
cur_node = new_head;
while (head){
head->next = cur_node->next;
head = head->next;
if (head)
cur_node->next = head->next;
cur_node = cur_node->next;
}
return new_head;
}
};
转载：https://blog.csdn.net/weixin_43993482/article/details/106222642