Problem:
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, next, random
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.
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]]
[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.
Solution:
This is a linked list copy problem with some twist.
In order to copy the linked list, we first clone the head node. Then we clone the head's next node, in order to update the next pointer. After that, we create a while loop, at each step, we move to the next node we just created, then we clone the next node of that node.
With random links, we have 2 difficulties:
1. how to access a random node with cost O(1).
2. how to access a random node that we haven't created yet.
For the difficulty 1, we can create a HashMap that maps from the old linked-list node to the new linked-list node. Therefore, with the random link in the old linked list node, we can find the random node, then use the random node to lookup the Hashmap in order to find the node we have cloned.
For the difficulty 2, we can create a the random node first before we create the next node.
import java.util.*;
class Solution {
Map<Node, Node> map = new HashMap<>();
public static void main(String[] args) {
//[7,null] ->[13,0]->[11,4]->[10,2]->[1,0]
Solution sol = new Solution();
Node head = sol.createRandomLL();
sol.print(head);
Node copy = sol.deepCopy(head);
sol.print(copy);
//print
}
private void print(Node head) {
while(head!=null) {
System.out.print("[" + head.val + ", ");
if(head.rand == null)
System.out.print("null] ->");
else
System.out.print(head.rand.val + "]->");
head = head.next;
}
System.out.println("null");
}
private Node createRandomLL() {
Map<Integer, Node> tmp = new HashMap<>();
int[] vals = new int[]{7, 13, 11, 10, 1};
Integer[] rands = new Integer[]{null, 0, 4, 2, 0};
for(int i = 0; i < vals.length; i++) {
tmp.put(i, new Node(vals[i], null, null));
}
for(int i = 0; i < vals.length; i++) {
Node curr = tmp.get(i);
curr.next = tmp.getOrDefault(i+1, null);
curr.rand = tmp.get(rands[i]);
}
return tmp.get(0);
}
private Node deepCopy(Node head) {
if(head != null) {
Node old = head;
Node newNode = copyNode(old);
while(old != null) {
newNode.next = copyNode(old.next);
newNode.rand = copyNode(old.rand);
old = old.next;
newNode = newNode.next;
}
return map.get(head);
}
return null;
}
private Node copyNode(Node head) {
if(head == null)
return null;
Node newNode = map.getOrDefault(head, new Node(head.val, null, null));
map.put(head, newNode);
return newNode;
}
class Node {
int val;
Node next;
Node rand;
public Node(int val, Node next, Node rand) {
this.val = val;
this.next = next;
this.rand = rand;
}
}
}
The time complexity is O(N) because we need to iterate the linked list once. The space complexity is O(N) due to the extra space the HashMap occupies.
