My java solution with O(n) time and O(n) space


  • 0
    L
    public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null) return null;
        HashMap<RandomListNode,RandomListNode> hash1=new HashMap<RandomListNode,RandomListNode>();
        HashMap<RandomListNode,RandomListNode> hash2=new HashMap<RandomListNode,RandomListNode>();
        RandomListNode node1,new_head,node_temp;
        node_temp=head;
        node1=new RandomListNode(head.label);
        new_head=node1;
        hash1.put(node_temp,node1);
        while(node_temp!=null) {
            if(node_temp.next!=null) {
                RandomListNode temp=new RandomListNode(node_temp.next.label);
                node1.next=temp;
                hash1.put(node_temp.next,node1.next);
            }else {node1.next=null;}
            node_temp=node_temp.next;
            node1=node1.next;
        }
        node_temp=head;
        while(node_temp!=null) {
            hash2.put(node_temp,node_temp.random);
            node_temp=node_temp.next;
        }
        node_temp=head;RandomListNode n=null;
        while(node_temp!=null) {
            n=hash2.get(node_temp);
            if(n==null) hash1.get(node_temp).random=null;
            else {
                hash1.get(node_temp).random=hash1.get(n);
            }
            node_temp=node_temp.next;
        }
        return new_head;
    }
    }

Log in to reply
 

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