题目
https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
本题的意思是复制一个链表并返回，这个链表与一般链表不同的是多了一个 random 指针。
在这里，复制的意思是指 深拷贝（Deep Copy），类似我们常用的“复制粘贴”，事实上，与此对应的还有 浅拷贝，它们的区别是：
解法
算法(迭代)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public Node copyRandomList(Node head) {
HashMap<Node,Node> map = new HashMap<>();
Node cur=head;
while(cur!=null){
map.put(cur,new Node(cur.val));
cur=cur.next;
}
cur = head;
while(cur!=null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
|
方法：DFS & BFS
图的基本单元是 顶点，顶点之间的关联关系称为 边，我们可以将此链表看成一个图：
1
2
3
4
5
6
7
8
9
10
11
12
13
| public Node copyRandomList3(Node head) {
Map<Node, Node> used = new HashMap<>();
return dfs(head, used);
}
Node dfs(Node head, Map<Node, Node> used) {
if (head == null) return null;
if (used.containsKey(head)) return used.get(head);
Node res = new Node(head.val);
used.put(head, res);
res.next = dfs(head.next, used);
res.random =dfs(head.random, used);
return res;
}
|
分解
1
2
3
| // 1. 复制每一个节点，使得复制后的节点都在当前节点的下一个节点
// 2. 原生链表的节点的指向任意节点，使复制的节点也都指向某一任意节点
// 3. 重新连接节点，把原生节点重新连接起来，把克隆后的节点连接起来
|
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
| public Node copyRandomList(Node head) {
if (head == null) return null;
copy(head);
randomDirect(head);
return reList(head);
}
private void copy(Node pNode) {
while (pNode != null) {
Node cloneNode = new Node(pNode.val);
Node nextNode = pNode.next;
pNode.next = cloneNode;
cloneNode.next = nextNode;
pNode = cloneNode.next;
}
}
private void randomDirect(Node pNode) {
while (pNode != null) {
Node cloneNode = pNode.next;
if (pNode.random != null) {
Node direct = pNode.random;
cloneNode.random = direct.next;
}
pNode = cloneNode.next;
}
}
private Node reList(Node pNode) {
Node cloneNode = pNode.next;
Node cloneHead = cloneNode;
pNode.next = cloneNode.next;
pNode = pNode.next;
while (pNode != null) {
cloneNode.next = pNode.next;
pNode = pNode.next.next;
pNode = pNode.next;
cloneNode = cloneNode.next;
}
return cloneHead;
}
|
