当前位置: 代码迷 >> J2SE >> leetcode刷题的时候碰到的一个有关问题,所有积分都给出去了
  详细解决方案

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

热度:37   发布时间:2016-04-23 20:05:15.0
leetcode刷题的时候碰到的一个问题,所有积分都给出去了
题目: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, 还不是太了解,抛个砖吧