Deep copy类型题总结

Deep copy类型题总结

这种类型题不难,只有两道代表类型题,一道是deep copy linkedlist,一道是deep copy graph。

最直观的想法就是就是使用HashMap,首先把node都先copy一遍,然后再连接他们。

提升一点的做法是使用dfs,在copy的过程中边copy边连接。注意,对于使用dfs copy graph我们不需要visited[]数组,我们可以直接通过判断Map中有没有该node来确认是否visited。

对于copy linkedlist,有一个提升空间复杂度的做法。Follow Up 如果不适用额外的辅助存储空间

第一步:将每个节点复制并插入相邻节点中。如1->2->3->NULL变为:1->1’->2->2’->3->3’->NULL。

第二步:接下来连接Random指针,如果存在一条Random指针从A指向B,那么将A->next的Random指针指向B->next。

第三步:将链表拆开。A=head, A’=head->next; A->next=A->next->next;A’->next=A’->next->next; …

时间复杂度O(n),额外空间复杂度O(1)

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
50
51
52
53
54
55
56
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;

public Node() {}

public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
if(head==null)
return null;
Node cur = head;
while(cur!=null){
Node newNode = new Node(cur.val);
newNode.next = cur.next;
cur.next = newNode;
cur = cur.next.next;
}

cur = head;
while(cur!=null){
if(cur.random!=null){
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}

Node newNode = new Node();
Node newNode2 = new Node();
Node n2 = newNode2;
Node n1 = newNode;
cur = head;
while(cur!=null){
n1.next = cur;
n2.next = cur.next;
cur = cur.next.next;
n1 = n1.next;
n2 = n2.next;
n1.next = null;
n2.next = null;
}

return newNode2.next;


}
}