Java solution with only one iteration and time complexity O(N)


  • 0
    M
    public RandomListNode copyRandomList(RandomListNode head) {
            Map<RandomListNode, RandomListNode> map = new HashMap<>();
            
            RandomListNode dummy = new RandomListNode(-1);
            
            RandomListNode curr = head, prev = dummy;
            while(curr != null) {
                
                RandomListNode newNode = null;
                if(map.containsKey(curr)) {
                    newNode = map.get(curr);
                } else {
                    newNode = new RandomListNode(curr.label);
                    map.put(curr, newNode);
                }
                prev.next = newNode;
                
                if(curr.random != null) {
                    RandomListNode newRandom = null;    
                    if(map.containsKey(curr.random)) {
                        newRandom = map.get(curr.random);
                    } else {
                        newRandom = new RandomListNode(curr.random.label);
                        map.put(curr.random, newRandom);
                    }
                    newNode.random = newRandom;
                }
                prev = newNode;
                curr = curr.next;
            }
            
            return dummy.next;
        }
    

Log in to reply
 

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