My recursive java O(n) solution, visiting each node once


  • 0
    /**
     * Definition for singly-linked list with a random pointer.
     * class RandomListNode {
     *     int label;
     *     RandomListNode next, random;
     *     RandomListNode(int x) { this.label = x; }
     * };
     */
    public class Solution {
        Map<RandomListNode, RandomListNode> map;
        public RandomListNode copyRandomList(RandomListNode head) {
            if(head == null)    
                return null;
            map = new HashMap<RandomListNode,RandomListNode>();
            
            return completeNode(head);
        }
        
        RandomListNode completeNode(RandomListNode n){
            if(n == null)    
                return null;
            if(map.containsKey(n))
                return map.get(n);
            else{
                RandomListNode copy = new RandomListNode(n.label);
                map.put(n,copy);
                copy.next = completeNode(n.next);
                copy.random = completeNode(n.random);
                return copy;
            }
        }
    }
    

Log in to reply
 

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