# [LeetCode 138] Copy List With Random Pointer

### Question

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.

### Stats

 Adjusted Difficulty 4 Time to use 20 minutes

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This is not a difficult question, however I mark it as difficulty level “4” because there are 2 solution, the second of which is hard to think of.

### Solution

Solution 1 which is my initial idea is using HashMap to store mappings from original nodes to copied nodes. This solution become exactly same as another question “Clone Graph”, only easier. It works fine.

However such solution uses O(n) extra space. Can we do it with less space?

Solution 2 is a in-place method which directly creates the copied list. It is well explained in here:

1. Create a copy of first node and insert it between Node 1 & Node 2 in original list. Then create a copy of second node and insert it between Node 2 & Node 3… Continue in this fashion
2. Set random link of the copied nodes (by referring to original.random.next)
3. Restore the original and copied lists (and return answer)

This solution (although uses 3 while-loops) is O(n) and O(1) extra space.

### Code

First, my solution using HashMap

``````public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
HashMap<RandomListNode, RandomListNode> map =
new HashMap<RandomListNode, RandomListNode>();
while (orin != null) {
if (orin.next != null) {
if (!map.containsKey(orin.next))
map.put(orin.next, new RandomListNode(orin.next.label));
cp.next = map.get(orin.next);
}
if (orin.random != null) {
if (!map.containsKey(orin.random))
map.put(orin.random, new RandomListNode(orin.random.label));
cp.random = map.get(orin.random);
}
orin = orin.next;
cp = cp.next;
}
}
``````

Second, constent space solution

``````public RandomListNode copyRandomList(RandomListNode head)  {
return null;
}
// copy each node and append right after original node
while (p != null)  {
RandomListNode cp = new RandomListNode(p.label);
cp.next = p.next;
p.next = cp;
p = p.next.next;
}
// now set random pointer of all copied nodes
while (p != null)  {
if (p.random != null)  {
p.next.random = p.random.next;
}
p = p.next.next;
}
// now restore original list, and connected all copied nodes
while (m != null)  {
if (n.next == null)  {
m.next = null;
m = null;
}
else  {
m.next = n.next;
n.next = n.next.next;
m = m.next;
n = n.next;
}
}
return ans;
}
``````