For Java, I think my solution is O(n), what kind of solution can reach 2 ms or even 1 ms?


  • 2
    B
    Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
    
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
    
        if (map.containsKey(head)) {
            return map.get(head);
        }
        
        RandomListNode newHead = new RandomListNode(head.label);
        map.put(head, newHead);
        
        newHead.next = copyRandomList(head.next);
        newHead.random = copyRandomList(head.random);
        return newHead;
    }

  • 0
    H

    What's the space consumption?


  • 0
    B

    The space is O(n). My solution takes about 5ms.


Log in to reply
 

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