O(n) Time, O(n) Space, One Iteration Java Solution with Hash Table


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

Log in to reply
 

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