What's wrong with my Java code using HashMap to reconstruct the random pointer?


  • 0
    C

    my code gets Wrong Answer

    Input: {-1,#}
    Output: {-1,-1}
    Expected: {-1,#}

    public RandomListNode copyRandomList(RandomListNode head) {
       if(head==null)
    	   return null;
    
       //maping the original node to its copied version
    
       Map<RandomListNode,RandomListNode> map=new HashMap<>();
    
       //following is the normal copy without copying the random pointer
    
       RandomListNode head2=new RandomListNode(head.label);
       map.put(head, head2);
       RandomListNode p1=head,p2=head2;
       while(p1.next!=null) {
    	   p2.next=new RandomListNode(p1.next.label);
    	   p1=p1.next;
    	   p2=p2.next;
    	   map.put(p1,p2);
       }
    
       //rebuild the random pointer
    
       p1=head;
       p2=head2;
       while(p2!=null) {
    	   p2.random=map.get(p1);
    	   p1=p1.next;
    	   p2=p2.next;
       }
       return head2;
    

    }


  • 0
    M

    You update the map (map.put(p1,p2)) after you increment the pointers p1 and p2..

    BTW I have done the exact same implementation and I can tell you the performance of this approach is not optimal (although it is accepted).


Log in to reply
 

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