leetcode刷题的时候碰到的一个问题，所有积分都给出去了

Question

java leetcodehashmap

Answer 1

亲，你这是要实现类似链表的结构吗，感觉好乱呀。很明显，节点间的引用有问题。建议你看看<<JAVA数据结构和算法>>里面会有你想要的

Answer 2

此题主要考查图的DFS，但注意到，有可能不是"有向无环图"，所以要用hashMap存储已经复制过的节点。下面是代码，已经AC。 public RandomListNode copyRandomList(RandomListNode head) {
    Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
    return dfs(head, map);
} public RandomListNode dfs(RandomListNode head, Map<RandomListNode, RandomListNode> map) {
    if (head == null) {
        return null;
    }
    if (map.containsKey(head)) {
        return map.get(head);
    }
    RandomListNode node = new RandomListNode(head.label);
    map.put(head, node);
    node.next = dfs(head.next, map);
    node.random = dfs(head.random, map);
    return node;
}

Answer 3

跑过，结果就是
running time error
Last executed input: {}
但是一开是我进行了null校验

Answer 4

这个和我的代码效率应该是一样的，不知道的就是为什么我已经经过了 null 校验，但是却出现
running time error
Last executed input: {}

Answer 5

一、关于"很多题都是这个结果"，个人感觉是你加上了不必要的set、get，这是一个不太好 习惯，可以参考参考jdk的linkedList、hashMap等等，它的节点类几乎没有任何get、set,都是"node.next=xxx"之类的代码，原因之一就是:所有的Json库解析，都是通过get、set完成，如果是linkedList这样的双链表的节点写上了get、set，无论遇到Apache的json还是goggle的gson，都会出现死循环。注意，作为一个ojer，追求的是简洁，建议不要写不必要的set、get。
二、如果你的思路正确，那么24、25行应该是random，而不是next，这应该笔误
三、注意有可能"带环"。带环的话，next、random下去，最后都能取到自身，你的11、23行对null的判断就有可能没有用，就会出现死循环，这估计是rte的原因。我看了非递归的题解，比你的这个要复杂些，你可能有细节没有注意到，所以建议用DFS的思想去解决。

Answer 6

我觉得是你在RandomListNode class 里面定义了自己的方法，他们就跑不了了。
我的理解是leetcode 给出的这个类的定义是不能自己改的。
刚刚接触Leetcode, 还不是太了解，抛个砖吧

Answer 7

非常感谢，我把LinkedList的源码看来一下，很有启发是这个问题

Answer 8

非递归解，比楼主的要简单，比dfs稍微容易理解一些。已经提交通过。
一个要注意的地方是HashMap，因为题目中RandomListNode没有重写hashCode和equals函数，所以用HashMap是可以的，否则就会出问题（不同的node可以有相同的label，会被误判为同一个node）。还是用IdentityHashMap最安全。
import java.util.IdentityHashMap;
import java.util.Map;
public RandomListNode copyRandomList(RandomListNode head) {
    Map<RandomListNode, RandomListNode> m = 
        new IdentityHashMap<RandomListNode, RandomListNode>();
    RandomListNode newHead = getCopy(m, head);
    RandomListNode current = newHead;
    while(head != null) {
        current.next = getCopy(m, head.next);
        current.random = getCopy(m, head.random);
        head = head.next;
        current = current.next;
    }
    return newHead;
}private RandomListNode getCopy(Map<RandomListNode, RandomListNode> cache, RandomListNode node)
{
    if(node == null) return null;
    RandomListNode v = cache.get(node);
    if(v == null) {
        v = new RandomListNode(node.label);
        cache.put(node, v);
    }
    return v;
}