利用HashMap保存一种映射关系

138. Copy List with Random Pointer

建立映射+遍历原来的链表获取关系

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
        RandomListNode p = head;
        //copy all the nodes
        while(p != null){
            RandomListNode newNode = new RandomListNode(p.label);
            map.put(p,newNode);
            p = p.next;
        }
        //Go over again and connect each nodes!
        p = head;
        while(p != null){
            map.get(p).next = map.get(p.next);
            map.get(p).random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
}

133. Clone Graph

同样是建立原来的Node和新的Node之间的映射 然后我们遍历原来的Node 建立新的结点 + 建立邻居关系不同于链表的这里要进行图的遍历 下面就是BFS/DFS的内容了

BFS:

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null)return null;
        UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
        HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
        map.put(node,copy);
        Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
        q.offer(node);
        while(!q.isEmpty()){
            UndirectedGraphNode cur = q.poll();
            for(UndirectedGraphNode i: cur.neighbors){
                if(!map.containsKey(i)){
                    UndirectedGraphNode newNode = new UndirectedGraphNode(i.label);
                    map.put(i,newNode);
                    q.offer(i);
                }
                map.get(cur).neighbors.add(map.get(i));
            }
        }
        return copy;
    }
}

DFS: 想象这个函数返回的就是该点的结果 运用到邻居节点上 注意函数什么时候返回

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
        return dfs(node,map);
    }
    public UndirectedGraphNode dfs(UndirectedGraphNode node,HashMap<UndirectedGraphNode,UndirectedGraphNode> map){
        if(node == null)return null;
        else if(map.containsKey(node)){
            return map.get(node);
        }
        else
        {
            UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
            map.put(node,newNode);
            for(UndirectedGraphNode neighbor: node.neighbors){
                newNode.neighbors.add(dfs(neighbor,map));
            }
            return newNode;
        }
    }
}