My Java solution using map got accepted but seems incorrect.


  • 0
    C

    I tried using the HashMap solution to first record all nodes with their random pointer to HashMap, then the next scan duplicate each node, and retrieve random pointer from HashMap, attach it to the copied node. Somehow I think there's something wrong with the random pointer copy, but it's still got accepted.

    public RandomListNode copyRandomList_wrong(RandomListNode head) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode ret = dummy;
        RandomListNode bak = head;
        
        while(bak!=null){
            map.put(bak, bak.random);
            bak = bak.next;
        }
        
        while(head!=null){
            dummy.next = new RandomListNode(head.label);
            RandomListNode node = map.get(head);
            /*!!!problem: I think it's just value copy of the random pointer, 
             the next node of original random pointer points to NOT get copied. */
            dummy.next.random = node==null?null:new RandomListNode(node.label); 
            dummy = dummy.next;
            head = head.next;
        }
        return ret.next;
    }

  • 0
    R

    My accept solution

    import java.util.Hashtable; 
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            Hashtable<RandomListNode,Integer> htIndex = new Hashtable<RandomListNode,Integer>();
            Hashtable<Integer,RandomListNode> newRandom = new Hashtable<Integer,RandomListNode>();
            int index = 0;
            if ( head != null ) {
                RandomListNode newH = new RandomListNode(head.label);
                RandomListNode loop = head;
                RandomListNode newI = newH;
                newRandom.put(index,newI);
                htIndex.put(loop,index++);
                while ( true ) {
                   loop = loop.next;
                   if ( loop == null ) {
                       break;
                   }
                   newI.next = new RandomListNode(loop.label);
                   newI = newI.next;
                   newRandom.put(index,newI);
                   htIndex.put(loop,index++);
                }
                loop = head;
                newI = newH;
                if ( loop.random != null ) {
                    newI.random = newRandom.get(htIndex.get(loop.random));
                }
                while ( true ) {
                    loop = loop.next;
                    newI = newI.next;
                    if ( loop == null ) {
                        break;
                    }
                    if ( loop.random != null ) {
                        newI.random = newRandom.get(htIndex.get(loop.random));
                    }
                }
                return newH;
            }
            return null;
        }
    }

Log in to reply
 

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