Why stackoverflow exception?


  • 0
    A

    The code 1 couldn't pass, but code 2 can pass.

    The only difference is Map<Integer, RandommListNode> and HashMap<Integer, RandommListNode>

    Anyone has idea?

    code 1:

    public static RandomListNode copyRandomList(RandomListNode node) {
        return copyHelper(node, new HashMap<>());
    }
    
    public static RandomListNode copyHelper(RandomListNode head, Map<Integer, RandomListNode> hm) {
        if (head == null) {
            return null;
        }
        if (hm.containsKey(head.label)) {
            return hm.get(head.label);
        }
        RandomListNode node = new RandomListNode(head.label);
        hm.put(node.label, node);
        node.next = copyHelper(head.next, hm);
        node.random = copyHelper(head.random, hm);
        return node;
    }
    

    Code 2:

    public static RandomListNode copyRandomList(RandomListNode node) {
        return copyHelper(node, new HashMap<>());
    }
    
    public static RandomListNode copyHelper(RandomListNode head, HashMap<Integer, RandomListNode> hm) {
        if (head == null) {
            return null;
        }
        if (hm.containsKey(head.label)) {
            return hm.get(head.label);
        }
        RandomListNode node = new RandomListNode(head.label);
        hm.put(node.label, node);
        node.next = copyHelper(head.next, hm);
        node.random = copyHelper(head.random, hm);
        return node;
    }

  • 0
    E

    The same thing happens in my case, too!

    Code gets stack overflow runtime error, uses HashMap.

    Changed it to Map and it works. I am really curious about these two data structures.


  • 0
    A

    @eyeabhi weird I thought map would pass and hashmap won't pass. I did some research days ago. You can google invokevirtual vs invokeinterface. Basically locating interface method takes o(n) time, but locating class method takes o(1) time. This is one of guess.


  • 1

    @allenlipeng47 Next time actually you can just paste your complete code for others easier checking.

    Here is a solution I retrieved from your HashMap solution.

    public class Solution {
        public static RandomListNode copyRandomList(RandomListNode node) {
        return copyHelper(node, new HashMap<>());
    }
    
    public static RandomListNode copyHelper(RandomListNode head, HashMap<RandomListNode, RandomListNode> hm) {
        if (head == null) {
            return null;
        }
        if (hm.containsKey(head)) {
            return hm.get(head);
        }
        RandomListNode node = new RandomListNode(head.label);
        hm.put(head, node);
        node.next = copyHelper(head.next, hm);
        node.random = copyHelper(head.random, hm);
        return node;
    }
    }
    

    I just replace the former label to the current object which I think can be more robust.


  • 0
    A

    @LHearen Thank you! This is a good point. It passed. hascode of RandomListNode will be the hashcode of the reference address.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.