Java O(N) space with 1 iteration only


  • 0
    Z

    There is no need to loop through the list twice, store the nodes already seen as the map's keys and put their corresponding copied nodes as the values. Every time checking a node, search map to get the copied node or make a deep copy if not found. The same with random node.

    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
    	HashMap<RandomListNode, RandomListNode> map = new HashMap<>();  //map for old node -> new node
    	if (head == null)
    	    return null;
    	// put null node mapping
    	map.put(null, null);
    	//Set up dummy head for new list
    	RandomListNode dummy = new RandomListNode(-1);
    	RandomListNode prev = dummy;
            //Define current node
            RandomListNode cur;
            while(head!=null){
                if(!map.containsKey(head)){ //unseen node, make a deep copy and put into map
                    cur = new RandomListNode(head.label);
                    map.put(head,cur);
                }else{  //seen node, extract the node from map
                    cur = map.get(head);
                }
                if(map.containsKey(head.random)){   //seen random node, link the corresponding nodes
                    cur.random = map.get(head.random);
                }else{  //unseen random node, make deep copy then link them, put them into map
                    cur.random = new RandomListNode(head.random.label);
                    map.put(head.random,cur.random);
                }
                prev.next = cur;
                prev = prev.next;
                head = head.next;
            }
    	return dummy.next;
        }
    }
    

Log in to reply
 

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