This is my solution with O(n) complex, and only scan once. Welcome to discuss.


  • 0
    H
    public RandomListNode copyRandomList(RandomListNode head) 
    {
    	if(head == null)
    		return null;
    
    	HashMap<RandomListNode,RandomListNode> hashMap = new HashMap<RandomListNode,RandomListNode>();
    	
    	RandomListNode headNode = null;
    	RandomListNode tailNode = null;
    	
    	for(RandomListNode node = head; node != null; node = node.next)
    	{
    		RandomListNode newNode;
    		if(!hashMap.containsKey(node))
    		{
    			newNode = new RandomListNode(node.label);
    			hashMap.put(node,newNode);
    		}
    		else
    			newNode = hashMap.get(node);
    		
    		RandomListNode random = node.random;
    		if(hashMap.containsKey(random))
    		{
    			newNode.random = hashMap.get(random);
    		}
    		else if(random == null)
    		{
    			newNode.random = null;
    		}
    		else
    		{
    			RandomListNode newRandom = new RandomListNode(random.label);
    			hashMap.put(random,newRandom);
    			newNode.random = newRandom;
    		}
    		
    		if(node != head)
    		{
    			tailNode.next = newNode;
    			tailNode = newNode;
    		}
    		else
    		{
    			headNode = newNode;
    			tailNode = newNode;
    		}
    	}
        return headNode;
    }
    

    The main difficulty is how to obtain the object's reference that random pointer points to. We can use a hashmap to store such a pair of values: the source node and its corresponding copy node.


  • 0
    D

    Hi there :
    I don't think you solution can fix this problem. Do you pass the test?
    think about the data like this.

    a->b-> c->d-> e->f
    |
    g
    |
    h
    |
    i
    as the picture show . we can think -> is node.next , | is node .random . in this test data I think you will miss the node h and i.


  • 0
    H

    Don't doubt, I passed the test. I think you didn't understand this question fully, the random must be one node in this link.


Log in to reply
 

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