Article From:https://www.cnblogs.com/strengthen/p/9967399.html

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.

Given a linked list, each node contains an additional random pointer that can point to any node or empty node in the linked list.

Requires that a deep copy of this list be returned.

1ms

``` 1 /**
2  * Definition for singly-linked list with a random pointer.
3  * class RandomListNode {
4  *     int label;
5  *     RandomListNode next, random;
6  *     RandomListNode(int x) { this.label = x; }
7  * };
8  */
9 public class Solution {
10     public RandomListNode copyRandomList(RandomListNode head) {
11         RandomListNode res = new RandomListNode(0);
12         RandomListNode p = res;
14         while (curr != null) {
15             p.next = clone(curr);
16             curr = curr.next;
17             p = p.next;
18         }
19         return res.next;
20     }
21
22     private RandomListNode clone(RandomListNode node) {
23         RandomListNode newNode = new RandomListNode(node.label);
24         if (node.random != null)
25             newNode.random = new RandomListNode(node.random.label);
26         return newNode;
27     }
28 }```

2ms

``` 1 /**
2  * Definition for singly-linked list with a random pointer.
3  * class RandomListNode {
4  *     int label;
5  *     RandomListNode next, random;
6  *     RandomListNode(int x) { this.label = x; }
7  * };
8  */
9 public class Solution {
10     public RandomListNode copyRandomList(RandomListNode head) {
14
18         while(curr!=null && curr.next!=null){
19             RandomListNode next = curr.next.next;
20             curr.next = next;
21             curr = next;
22
23             if(start.next!=null) {
24                 start.next = start.next.next;
25                 start = start.next;
26             }
27         }
28
30     }
31
34
36         while(curr!=null){
37             RandomListNode next = curr.next;
38             curr.next = new RandomListNode(curr.label);
39             curr.next.random = curr.random;
40             curr.next.next = next;
41             curr = next;
42         }
43     }
44
45     private void copyRandom(RandomListNode head) {
48         while(curr!=null && curr.next!=null){
49             RandomListNode next = curr.next.next;
50             if(curr.next!=null && curr.random!=null){
51                 curr.next.random = curr.random.next;
52             }
53             curr = next;
54         }
55     }
56 }```

2ms

``` 1 /**
2  * Definition for singly-linked list with a random pointer.
3  * class RandomListNode {
4  *     int label;
5  *     RandomListNode next, random;
6  *     RandomListNode(int x) { this.label = x; }
7  * };
8  */
9 public class Solution {
11     {
12         RandomListNode root = null, prev = null, rootIter = head;
13
14         while (rootIter != null)
15         {
16             RandomListNode newCopy = new RandomListNode(rootIter.label);
17             newCopy.next = null;
18             newCopy.random = null;
19
20             prev = rootIter;
21             rootIter = rootIter.next;
22
23             prev.next = newCopy;
24             newCopy.next = rootIter;
25             /* 'prev' points to previous rootIter whose 'next' will point
26             to the new copy of previous rootIter created in 'newCopy' */
27         }
29             root = null;
30
31         else
33
35         while (rootIter != null)
36         {
37             if (rootIter.random == null)
38                 rootIter.next.random = null;
39
40             else
41                 rootIter.next.random = rootIter.random.next;
42
43             rootIter = rootIter.next.next;
44         }
45
47         while (rootIter != null)
48         {
49             RandomListNode nextNode = rootIter.next.next;
50             if (nextNode != null)
51                 rootIter.next.next = nextNode.next;
52
53             rootIter.next = nextNode;
54             rootIter = nextNode;
55         }
56         return root;
57     }
58 }```

3ms

``` 1 /**
2  * Definition for singly-linked list with a random pointer.
3  * class RandomListNode {
4  *     int label;
5  *     RandomListNode next, random;
6  *     RandomListNode(int x) { this.label = x; }
7  * };
8  */
9 public class Solution {
10
11     private Map<RandomListNode,RandomListNode> visited = new HashMap<>();
12
13     public RandomListNode copyRandomList(RandomListNode head) {
15             return null;
16         }
17
20         }
21
22         RandomListNode newNode = new RandomListNode(head.label);
23         visited.put(head,newNode); //at this point in time, we have newed this node. does not matter if we need to recurse further to have it fully constructed. this is already copied. thus mark it as visited
24