Sharing my solution: O(n) complexity, O(1) space complexity, single iteration


  • -1
    S
         public class Solution {
        	public RandomListNode copyRandomList(RandomListNode head) {
        		if(head == null){
        			return null;
        		}
        		RandomListNode newHead = new RandomListNode(head.label);
        		RandomListNode loop = head;
        		Map<RandomListNode, RandomListNode> randomNodeMap = new HashMap<RandomListNode, RandomListNode>();
        		
        		RandomListNode newNode = newHead;
        		RandomListNode randomNewNode;
        		
        		while(null !=loop){
        			if(null != loop.random){
        				randomNewNode = new RandomListNode(loop.random.label);
        				newNode.random = randomNewNode;
        				if(!randomNodeMap.containsKey(loop.random)){
        					randomNodeMap.put(loop.random, newNode);
        				}
        			}
        			
        			if(null != loop.next){
        				if(randomNodeMap.containsKey(loop.next)){
        					newNode.next = randomNodeMap.get(loop.next).random;
        				}else{
        					newNode.next = new RandomListNode(loop.next.label);
        					newNode = newNode.next;
        				}
        			}else{
        				newNode.next = null;
        			}
        			loop = loop.next;
        		}
        		return newHead;
            }
        }
    
    
      [1]: http://C:%5CUsers%5CSudeesh%5CDesktop%5Cquestion.png

  • 0
    C

    It seems to use O(n) space rather than O(1) space, since you use a map to remember mapping relations.


Log in to reply
 

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