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)

/*
// 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;

        
    }
}