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 representingNode.valrandom_index: the index of the node (range from0ton-1) where random pointer points to, ornullif it does not point to any node.
Constraints
-10000 <= Node.val <= 10000Node.randomis null or pointing to a node in the linked list.Number of Nodes will not exceed 1000.
Approach
Links
GeeksforGeeks
YouTube
Examples
Input: head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
Output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
Input: head = [[1, 1], [2, 1]]
Output: [[1, 1], [2, 1]]
Input: head = [[3, null], [3, 0], [3, null]]
Output: [[3, null], [3, 0], [3, null]]
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.
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
Last updated
Was this helpful?