C# Hash Solution


  • 0

    1- Create a copy of each node and add source and copy nodes in a hash table or dictionary.
    2- Traverse the source and copy and get directly to the random node using hashtable.
    3- Update the random pointers in copy.

    ''''
    ''''
    public RandomListNode CopyRandomList(RandomListNode head) {
    RandomListNode copy= null;
    Dictionary<RandomListNode,RandomListNode> dic=new Dictionary<RandomListNode,RandomListNode>();

        RandomListNode h= head;
        RandomListNode c=null;
        RandomListNode r=null;
       
        while (h!= null)
        {
            
            RandomListNode n= new RandomListNode(h.label);
            
            if (c==null)  
            {
                copy=n;
            }             
            else
            {
                c.next=n;
            }
            c=n;  
            
            dic.Add(h,c);
            
            h=h.next;
            
        }
        
        c=copy;
        h=head;
        while(c!=null)
        {
            r=null;
            if (h.random!=null)
            {
                if (dic.TryGetValue(h.random,out r)){
                    c.random=r;
                }
            }
            h=h.next;
            c=c.next;
                
            
        }
       return copy; 
    }
    

    ''''


Log in to reply
 

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