Hash map for deep copy

A deep copy indicates all data and pointers are copied. The original object and the copied one don't depend on each other.

The Clone Graph and Copy List with Random Pointer can both be solved by using a hash map. Basically, the idea is to use the map to store the original node and the copied new node. For Clone Graph, we search the map for neighbor lists while for Copy List with Random Pointer, we search for the random node that the original node points to.

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Update: 2015 - 01 - 03

Use an arrayList to store the odd nodes, and use the map to store node - copy pairs. Start from the input node, pop its neighbor list and add its neighbors to the map and array.

The next step is to copy neighbor lists. Iterate in the list, get the new node from the map and copy the neighbors.

class UndirectedGraphNode {
      int label;
      List neighbors;
      UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); }
  };
 
public class CloneGraph {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null)
            return node;
        HashMap hm = new HashMap();
        List nodes = new ArrayList ();
        nodes.add(node);
        hm.put(node, new UndirectedGraphNode(node.label));
        int size = 0;
        while (size < nodes.size()) {
            UndirectedGraphNode tmp = nodes.get(size++);
            if (tmp.neighbors != null) {
                for (UndirectedGraphNode neighbor : tmp.neighbors) {
                    if (!hm.containsKey(neighbor)) {
                        hm.put(neighbor, new UndirectedGraphNode(neighbor.label));
                        nodes.add(neighbor);
                    }
                }
            }
        }
        for (UndirectedGraphNode no : nodes) {
            UndirectedGraphNode tmp = hm.get(no);
            if (no.neighbors != null) {
                tmp.neighbors = new ArrayList ();
                for (UndirectedGraphNode neighbor : no.neighbors) {
                    UndirectedGraphNode neighbor2 = hm.get(neighbor);
                    tmp.neighbors.add(neighbor2);
                }
            }
        }
        return hm.get(node);
    }
}

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

class RandomListNode {
      int label;
      RandomListNode next, random;
      RandomListNode(int x) { this.label = x; }
  };
 
public class CopyList {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null)
            return null;
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode pre = dummy;
        RandomListNode newNode;
        HashMap hm = new HashMap();
        while (head != null)
        {
            if (hm.containsKey(head))
                newNode = hm.get(head);
            else
            {
                newNode = new RandomListNode(head.label);
                hm.put(head, newNode);
            }
            if (head.random != null)
            {
                if (hm.containsKey(head.random))
                    newNode.random = hm.get(head.random);
                else
                {
                    newNode.random = new RandomListNode(head.random.label);
                    hm.put(head.random, newNode.random);
                }
            }
            pre.next = newNode;
            pre = newNode;
            head = head.next;
        }
        return dummy.next;
    }
}