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;
} }
|