# Shortest java O(1) space, why we need a map?

• ``````public class Solution {
while(first!=null)
{
if(first.next!=null)second.next=new RandomListNode(first.next.label);//copy next
else second.next=null;

if(first.random!=null)second.random=new RandomListNode(first.random.label);//copy random
else second.random=null;
first=first.next;
second=second.next;
}
}
}

``````

Why this question need a map?I think it is a very obvious and straightforward, my code pass the submission. is it wrong?

• Good one to copy "next" pointer, but not perfect one to copy "random" pointer.

Let's say you have a linked list, for Next pointer : 1 => 2 => 3
but for Random pointer: 1 = > 2 <= 3 (1 points to 2, 2 points to null, 3 points to 2)
Totally 3 nodes.

What you are asked to do is return this:
1 => 2 => 3 (=> for Next Pointer)
↓___↑____↓ (— for Random Pointer)

You do copy Next pointer correctly 1 => 2 => 3, but for Random Pointer. You actaully created additionally 2 Nodes with value 2.
1 => 2 => 3
↓ xxxxxxx ↓
2 xxxxxxx 2

Random Pointers of Node 1 and Node 3 point to another 2 nodes with value 2. Even though their values are the same, they are not the same Object.

If you do not understand this, try start with E and M difficulty and get familiar with Java first.

• In short, you are creating extra nodes equal to the number of non-null random pointers.
Your solution passes, because it's impossible for LeetCode to detect that extra space. However your interviewer won't fail to detect that :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.