Java O(n) with 1 pass, but why it's slow? 9ms


  • 0
    X
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
            RandomListNode h = head;
            while (h != null) {
                map.putIfAbsent(h,new RandomListNode(h.label));
                RandomListNode n = map.get(h);
                if (h.random != null) {
                    map.putIfAbsent(h.random, new RandomListNode(h.random.label));
                    n.random = map.get(h.random);
                }
                if (h.next != null) {
                    map.putIfAbsent(h.next, new RandomListNode(h.next.label));
                    n.next = map.get(h.next);
                }
                h = h.next;
            }
            return map.get(head);
        }
    }
    

  • 0
    X

    The usage of map.putIfAbsent() appears problematic, you are creating and throwing away a new RandomListNode object every time when it's NOT absent. And sometime two passes might have much simple logic.


Log in to reply
 

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