Copy List with Random Pointer
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.val
random_index
: the index of the node (range from0
ton-1
) where random pointer points to, ornull
if it does not point to any node.
Example 1:

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

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Example 4:
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.
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.
/*
// 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;
}
}
*/
// O(n) -> time && O(n) -> space.
class Solution {
public Node copyRandomList(Node head) {
HashMap<Node, Node> map = new HashMap<>();
Node current = head;
while (current != null) {
Node temp = new Node(current.val);
map.put(current, temp);
current = current.next;
}
Node ans = map.get(head);
current = head;
while (current != null) {
Node temp = map.get(current);
if (current.next != null)
temp.next = map.get(current.next);
if (current.random != null) {
temp.random = map.get(current.random);
}
current = current.next;
}
return ans;
}
}
//O(n) -> time and O(1) ->Space.
class Solution {
public Node copyRandomList(Node head) {
if(head==null)
return null;
Node current = head;
while (current != null) {
Node copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
current = head;
Node ans = head.next;
while (current != null) {
Node copy = current.next;
if (current.random != null)
copy.random = current.random.next;
current = copy.next;
}
current = head;
while (current != null) {
Node copy = current.next;
if (copy.next != null) {
current.next = copy.next;
copy.next = copy.next.next;
} else {
current.next = copy.next;
}
current = current.next;
}
return ans;
}
}
Last updated