对象克隆

作为一个程序员，一定听说过“深拷贝”和“浅拷贝”的概念。我们在“深”复制一个对象的时候，不但要新建当前的对象，当前对象引用的其他对象也要新建。在这个过程中，哈希表这个数据结构起到了不可替代的作用。下面我们一起来看一下它的神奇效果吧。

1. 复制链表

这个题目是leetcode138题。意思是一个链表，它的每一个结点除了具有一个next指针以外，还有一个random指针，这个指针可以指向链表中的任何一个结点，也可以指向null，现在我们需要把这样的一个链表整体克隆下来。这个问题的关键在于如何根据原有链表结点的random指针的指向，找到当前对应克隆结点的random应该指向谁。

如果我们可以把原有链表中任何一个结点和它在新的链表中的克隆结点对应起来，即我们设计一个数据结构，传入原链表的结点，就可以查询得到它在新链表中的对应的克隆结点，那么问题不就迎刃而解了吗？那么这个数据结构是啥？请大声说出他的名字。

哈希表

所以我们先按照next指针遍历一遍，得到原有链表中所有结点的克隆结点，并把这样的对应关系存到哈希表map 中。然后再次遍历我们刚才克隆得到的链表，对于新链表中的每一个结点nodeNew，与它对应的旧链表中的结点是nodeOld，那么nodeNew.random = map.get(nodeOld.random)。如下图所示：

代码如下：

import java.util.HashMap;

public class CloneRandomList {
    
    public static Node clone(Node head) {
        if(head == null) return null;
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head, ans = null, t = null;
        while(cur != null) {
            if(t == null) t = ans = new Node(cur.val);
            else t = t.next = new Node(cur.val);
            map.put(cur, t);// 哈希表记录对应关系
            cur = cur.next;
        }
        // 再次遍历，填充random指针
        for(t = ans, cur = head; t != null; t = t.next, cur = cur.next) {
            if(cur.random != null) t.random = map.get(cur.random);
        }
        return ans;
    }
    
    static class Node {
        int val;
        Node next, random;
        Node(int val) {
            this.val = val;
        }
    }
}

2. 复制图

这个题目是leetcode133题。给你一个使用邻接表法表示的无向连通图中的一个结点，请克隆这个图，返回所给结点的克隆结点。

怎么克隆一个图呢？首先克隆题目给出的这个结点，然后克隆它的所有邻接点。我们在克隆的时候，为了避免陷入死循环，如果一个结点被克隆过，那么我们把这个结点和它对应的克隆结点放在哈希表中维护。于是代码如下：

import java.util.List;
import java.util.ArrayList;

public class CloneGraph {
    
    HashMap<Node, Node> map = new HashMap<>();
    
    public static Node clone(Node node) {
        if(node == null) return null;
        Node clonedNode = map.get(node);
        if(clonedNode != null) return clonedNode;
        clonedNode = new Node(node.val);
        map.put(node, clonedNode);
        // 递归克隆其邻接点
        for(Node neighbor: node.neighbors) clonedNode.neighbors.add(clone(neighbor));
        return clonedNode;
    }
    
    static class Node {
        int val;
        List<Node> neighbors;
        Node(int val) {
            this.val = val;
            neighbors = new ArrayList<>();
        }
    }
}