Java O(n) solution


  • 181
    public RandomListNode copyRandomList(RandomListNode head) {
      if (head == null) return null;
      
      Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
      
      // loop 1. copy all the nodes
      RandomListNode node = head;
      while (node != null) {
        map.put(node, new RandomListNode(node.label));
        node = node.next;
      }
      
      // loop 2. assign next and random pointers
      node = head;
      while (node != null) {
        map.get(node).next = map.get(node.next);
        map.get(node).random = map.get(node.random);
        node = node.next;
      }
      
      return map.get(head);
    }

  • 0
    L

    nice solution


  • 0
    J

    easy to understand! thansk!


  • 0

    easy to understand.


  • 0
    Y

    Thanks you! it was easy to understand


  • 5
    E

    In the loop2. assign next and random pointers.
    We should check whether iter.next or iter.random is null or not!

    import java.util.Hashtable;
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if(head==null){
                return null;
            }
            
            Hashtable<RandomListNode,RandomListNode> ht= new Hashtable<RandomListNode,RandomListNode>();
            
            RandomListNode iter=head;
            while(iter!=null){
                ht.put(iter,new RandomListNode(iter.label));
                iter=iter.next;
            }
            
            iter=head;
            while(iter!=null){
                if(iter.next!=null){
                    ht.get(iter).next=ht.get(iter.next);
                }
                if(iter.random!=null){
                    ht.get(iter).random=ht.get(iter.random);    
                }
                iter=iter.next;
            }
            
            return ht.get(head);
        }
    }
    

  • 0
    R

    Nice solution :)


  • 6

    Clean solution, but I have some concerns when I thought about HashTables: What is RandomListNode's hashValue, is it Object's in-memory representation? Is it guaranteed to be unique for each object?

    For some followup, if the RandomListNode's a black-box, seems we cannot use this solution, cause its hash value computation is not transparent. Am I correct?


  • 1
    W

    @pinkfloyda Nice question, I wanna know too.


  • 1
    J

    @ernieho map.get(null) is null, so we can reduce the check


  • 0
    J

    @pinkfloyda I believe RandomListNode's hashCode() is not guaranteed to be unique. If two keys have the same hashCode(), then HashMap will try to solve this collision by using Separat chainning.


  • 0

    I've just condensed your solution by using for-loops here :)

       public RandomListNode copyRandomList(RandomListNode head) {
          if (head == null) return null;
    
          Map<RandomListNode, RandomListNode> map = new HashMap<>();
          for (RandomListNode ptr = head; ptr != null; ptr = ptr.next) {
             map.put(ptr, new RandomListNode(ptr.label));
          }
    
          for (RandomListNode ptr = head; ptr != null; ptr = ptr.next) {
             map.get(ptr).next = map.get(ptr.next);
             map.get(ptr).random = map.get(ptr.random);
          }
          return map.get(head);
       }
    

  • 0
    C

    One assumption with this code is that all the nodes pointed to by the random pointer can be reached through the next pointer as well. I would clarify this assumption in the real interview before presenting this answer or not make this assumption at all.


  • 0
    B

    @ernieho , you don't have to check the null value when using get() method of HashMap<>, because it will return null when you passing null as key (as long as there's no null as key in the map)


  • 0
    U

    @pinkfloyda Great question, when solving this problem I had the same concern, here I read that
    "Typically, hashCode() just returns the object's address in memory if you don't override it"

    Then if this is right, the solution @jeantimex proposed is correct, but anyway, if this is an interview, you should at least mention it when solving the problem and propose an alternative solution if this is not true


  • 0
    U

    Very clean and concise solution! Thanks!


  • 0
    S

    @jeantimex Very smart solution. Thank you for your sharing.


Log in to reply
 

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