A strange problem while using java


  • 0
    L
    public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode, RandomListNode> createdNode = new HashMap<RandomListNode, RandomListNode>();
        return copyRandomList(head, createdNode);
    }
    
    
    public RandomListNode copyRandomList(RandomListNode node, HashMap<RandomListNode, RandomListNode> createdNode) {
        if(node == null)
        {
            return null;
        }
        
        RandomListNode newNode = new RandomListNode(node.label);
    
        createdNode.put(node, newNode);
    
        newNode.next =copyRandomList(node.next, createdNode);
        
        RandomListNode newRandom = null;
        if(node.random != null)
        {
            newRandom = createdNode.get(node.random);
        }
        newNode.random = newRandom;
        
        return newNode;
        
    }
    

    }

    If I wrote code this, there would be a StackOverFlow problem at line"createdNode.put(node, newNode);"
    How ever, if the part "newNode.next =copyRandomList(node.next, createdNode);" to "RandomListNode test =copyRandomList(node.next, createdNode); "newNode.next = test ", the code passed all test cases. Is there any different between the two kinds of code?


  • 0
    D

    First of all, if you want to understand about StackOverflowError, you can take a look at here .

    If you look at the assignment operator carefully:

    newNode.next = copyRandomList(node.next, createdNode);   //(1)
    

    Upon a function call, what is put to the stack is the value on the left side, the values of parameters (in case of objects, the values are references). So using newNode.next assignment reference of newNode is also added to the stack. For the value (refrence) to "next", it is not be initialized so nothing is put to stack.

    In case of :

    RandomListNode test =copyRandomList(node.next, createdNode);  //(2)
    

    The test is not initialized, so nothing is put to stack.

    As you can see, in case (1), there is an extra amount of data is put into stack. And LeetCode limits the amount of stack you can use for your Solution!!!!

    To make the Solution passes , we can try to reduce the amount of data to put to stack. How? You can use the following code that I've modified yours:

    public class Solution {
        public HashMap<RandomListNode, RandomListNode> createdNode; 
        public RandomListNode copyRandomList(RandomListNode head) {
            createdNode = new HashMap<RandomListNode, RandomListNode>();
            return cc(head);
        }
        
        
        public RandomListNode cc(RandomListNode node) {
            if(node == null)
            {
                return null;
            }
        
            RandomListNode newNode = new RandomListNode(node.label);
        
            createdNode.put(node, newNode);
            
            newNode.next = cc(node.next);
           
            RandomListNode newRandom = null;
            if(node.random != null)
            {
                newRandom = createdNode.get(node.random);
            }
            newNode.random = newRandom;
        
            return newNode;
        
        }
    }
    

Log in to reply
 

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