138. Copy List with Random Pointer

Description

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Constraints

-10000 <= Node.val <= 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.

Approach

Examples

Input: head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

Output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

Solutions

// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

/**
 * Time complexity : O(N) where N is the number of nodes in the linked list.
 * Space complexity : O(N). If we look closely, we have the recursion stack 
 *    and we also have the space complexity to keep track of nodes already 
 *    cloned i.e. using the visited dictionary. But asymptotically, 
 *    the complexity is O(N).
 */

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> nodes = new HashMap();
        return helper(head, nodes);
    }
    
    private Node helper(Node node, Map<Node, Node> nodes) {
        if(node == null) return null;
        
        if(nodes.containsKey(node)) {
            return nodes.get(node);
        }
        
        Node newNode = new Node(node.val);
        nodes.put(node, newNode);
        
        newNode.next = helper(node.next, nodes);
        newNode.random = helper(node.random, nodes);
        
        return newNode;
    }
}

Follow up

Previous137. Single Number II Next139. Word Break

Last updated 5 years ago

hashtagDescription

hashtagConstraints

hashtagApproach

hashtagLinks

hashtagExamples

hashtagSolutions

hashtagFollow up