# No HashMap O(n) Java solution

• The idea is the same to the others. It needs to iterate the original list three times.
The in-text annotation should be more helpful

``````public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {

if (head==null) return null;

RandomListNode node = head;
//1. In-place copy: Copy new code, insert to the next position of original code

while(node!=null){
RandomListNode temp = new RandomListNode(node.label);//Copy
//Insert
temp.next=node.next;
node.next=temp;
//Move
node=temp.next;
}

//2. Assign the random
while(node!=null){
if (node.random!=null)node.next.random=node.random.next;
node=node.next.next;
}
//3.Split the sequence
RandomListNode ori = head;
RandomListNode nova = head.next;

while(ori!=null){
//Split
ori.next=ori.next.next;
if (nova.next!=null) nova.next=nova.next.next;
//Move
ori=ori.next;
nova=nova.next;
}
return node;

}
}``````

• I also didn't use hashMap, and only use one while loop, but time is 500+

``````public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null) {
return null;
}
RandomListNode result = new RandomListNode(head.label);
RandomListNode curr1 = head;
RandomListNode curr2 = result;

while(curr1 != null ) {
if(curr1.next != null) {
curr2.next = new RandomListNode(curr1.next.label);
}

if(curr1.random != null) {
curr2.random = new RandomListNode(curr1.random.label);
}
curr1 = curr1.next;
curr2 = curr2.next;
}
return result;
}
``````

}

• Your answer is not correct, random pointer may just points to another node in the linked list.

## Consider this example:

| |>
1 -> 2 -> 3 -> NULL
^ |
| |
-------

i.e. 1's random points to 2, 3' s random points to 2.
Try to run your code see what would happen.

• = =! my example is collapsed, let me describe: 1's next points to 2, 1's random points to 2; 2's next points to 3, 2's random is null; 3's next points to null, 3's random points to 2.

• I know what you mean. In your case, 2 is already there, when 1 randomly points to it again, I create another new node instead of previous one(2 in this case), when 3 randomly points to 2, I also create new node, but I should let 1 and 3 randomly point to 2, this means there should be only one 2's node..
Do you think I understand what you said? Thanks！ I think my code is not correct, but it passed all the test, it is weird...

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