题目:https://oj.leetcode.com/problems/copy-list-with-random-pointer/
my code:
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
RandomListNode newListHead = new RandomListNode(0);
RandomListNode realNewListHead = newListHead;
RandomListNode oldListHead = head;
int listSize = 0;
Map<RandomListNode, RandomListNode> locationMap = new HashMap<RandomListNode, RandomListNode>();
while (oldListHead!=null){
newListHead.setNext(new RandomListNode(oldListHead.getLabel()));
newListHead = newListHead.getNext();
locationMap.put(oldListHead, newListHead);
oldListHead = oldListHead.getNext();
listSize++;
}
// 最后会返回的节点
realNewListHead = realNewListHead.getNext();
oldListHead = head;
newListHead = realNewListHead;
while (oldListHead!= null){
newListHead.getRandom((RandomListNode)locationMap.get(oldListHead));
oldListHead = oldListHead.getNext();
newListHead = newListHead.getNext();
}
return realNewListHead;
}
}
class RandomListNode {
int label;
RandomListNode next, random;
public int getLabel() {
return label;
}
public void setLabel(int label) {
this.label = label;
}
public RandomListNode getNext() {
return next;
}
public void setNext(RandomListNode next) {
this.next = next;
}
public RandomListNode getRandom(RandomListNode randomListNode) {
return random;
}
public void setRandom(RandomListNode random) {
this.random = random;
}
RandomListNode(int x) { this.label = x; }
}
运行结果是:
running time error
Last executed input: {}
求解答,很多题都是这个结果,求解答
------解决思路----------------------
一、关于"很多题都是这个结果",个人感觉是你加上了不必要的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的思想去解决。
------解决思路----------------------
我觉得是你在RandomListNode class 里面定义了自己的方法,他们就跑不了了。
我的理解是leetcode 给出的这个类的定义是不能自己改的。
刚刚接触Leetcode, 还不是太了解,抛个砖吧