My accepted Java code. O(n) but need to iterate the list 3 times

• The idea is:
Step 1: create a new node for each existing node and join them together
eg: A->B->C will be A->A'->B->B'->C->C'

Step2: copy the random links: for each new node n', n'.random = n.random.next

Step3: detach the list: basically n.next = n.next.next; n'.next = n'.next.next

Here is the code:

``````/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
return null;
}
while (n!=null){
RandomListNode n2 = new RandomListNode(n.label);
RandomListNode tmp = n.next;
n.next = n2;
n2.next = tmp;
n = tmp;
}

while(n != null){
RandomListNode n2 = n.next;
if(n.random != null)
n2.random = n.random.next;
else
n2.random = null;
n = n.next.next;
}

//detach list
while(n2 != null && n != null){
n.next = n.next.next;
if (n2.next == null){
break;
}
n2.next = n2.next.next;

n2 = n2.next;
n = n.next;
}

}
}``````

• Using a HashMap and there are n recursive calls.

``````public class Solution {
HashMap<RandomListNode,RandomListNode> nodemap = new HashMap<RandomListNode,RandomListNode>();
}
public RandomListNode copyListHelper(RandomListNode head, HashMap<RandomListNode,RandomListNode> nodemap)  {
return ret;
}
``````

• same idea but with concise hashmap code.

``````public RandomListNode copyRandomList(RandomListNode head) {
//<original, clone>
HashMap<RandomListNode, RandomListNode> maps = new HashMap<RandomListNode, RandomListNode>();
while(null != cursor){
maps.put(cursor, new RandomListNode(cursor.label));
cursor = cursor.next;
}
while(null != cursor){
maps.get(cursor).random = maps.get(cursor.random);
cursor = cursor.next;
}
while(null != cursor){
maps.get(cursor).next = maps.get(cursor.next);
cursor = cursor.next;
}
}``````

• I had something similar, but it gives a StackOverflow error. This answer is not accepted, even though it may well should be :-).

• Good method. But I think you don't need three iteration now, two is enough. We can set next and random in one iteration together.

• Stack overflow

• What @flyinghx61 said is true. It can be done in two iterations.

``````public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
Map<RandomListNode, RandomListNode> map = new HashMap<>();
while (p != null) {
map.put(p, new RandomListNode(p.label));
p = p.next;
}

while (p!= null) {
map.get(p).random = map.get(p.random);
map.get(p).next = map.get(p.next);
p = p.next;
}
}``````

• Using hashmap is surely simple, but it's inefficient to use an Object as key. I vote for the one without hashmap which runs much faster when testing. Here's my more concise and easy-to-understand Java code.

``````public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
while (p != null) {
RandomListNode pClone = new RandomListNode(p.label);
pClone.next = p.next;
p.next = pClone;
p = pClone.next;
}

while (p != null) {
p.next.random = p.random == null ? null : p.random.next;
p = p.next.next;
}

while (p != null) {
RandomListNode pClone = p.next;
p.next = pClone.next;
pClone.next = pClone.next == null ? null : pClone.next.next;
p = p.next;
}
}``````

• Brilliant solutions! Thanks for sharing!

• For the detach part, I tried to use the dummy node to make it easier. But I cannot even pass the first test case. Can anyone tell me why this happens?

``````//detach
RandomListNode dummy = new RandomListNode(0);
}

//get result
return dummy.next;
``````

• Why my below code got accepted by OJ since I did not use map and also not use three iterations with O(n). Any advises?

return null;
}
RandomListNode result = new RandomListNode(-1);
result.next = current;

``````	while(head != null){
current.next = next;
}else{
current.next = null;
}
current.random = random;
}else{
current.random = null;
}
current = current.next;
}
return result.next;
}``````

• Why three or even two iterations? I could write it in one iteration:

Brilliant Solution with only One Iteration - Using Dummy Node and Dictionary

• @FreshMeYo Please see my below solution, where I have used Dummy node and solved the question in one iteration:

Brilliant Solution with only One Iteration - Using Dummy Node and Dictionary

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