138. Copy List with Random Pointer

题目：

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.

链接：https://leetcode.com/problems/copy-list-with-random-pointer/#/description

4/16/2017

自己想不出来，答案是抄的。

对于链表的题，需要把递归当成一种常见的思路！而且，一定要考虑到输入的各种陷阱！比如此题，map里一定要存旧的和新的node而不是旧label新node。最重要的是，链表一定要想到是否有circle！一开始的解法对circle不适用我觉得不是大问题，然而，一定要沟通出来，比方说在leetcode答案看下来之后，只有这种方法是对circle有效的。

 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     Map<RandomListNode, RandomListNode> visited = new HashMap<>();
11 
12     public RandomListNode copyRandomList(RandomListNode head) {
13         if(head == null)
14             return head;
15         if(visited.containsKey(head))
16             return visited.get(head);
17         RandomListNode root = new RandomListNode(head.label);
18         visited.put(head, root);
19         
20         root.next = copyRandomList(head.next);
21         root.random = copyRandomList(head.random);
22         return root;
23     }
24 }

其他的各种好思路，然而，只对于没有circle的list有用：

这个解法是将旧的和新的放在一起，通过三次遍历重塑两个list，充分利用了next的特性

https://discuss.leetcode.com/topic/7594/a-solution-with-constant-space-complexity-o-1-and-linear-time-complexity-o-n

 1 public RandomListNode copyRandomList(RandomListNode head) {
 2     RandomListNode iter = head, next;
 3 
 4     // First round: make copy of each node,
 5     // and link them together side-by-side in a single list.
 6     while (iter != null) {
 7         next = iter.next;
 8 
 9         RandomListNode copy = new RandomListNode(iter.label);
10         iter.next = copy;
11         copy.next = next;
12 
13         iter = next;
14     }
15 
16     // Second round: assign random pointers for the copy nodes.
17     iter = head;
18     while (iter != null) {
19         if (iter.random != null) {
20             iter.next.random = iter.random.next;
21         }
22         iter = iter.next.next;
23     }
24 
25     // Third round: restore the original list, and extract the copy list.
26     iter = head;
27     RandomListNode pseudoHead = new RandomListNode(0);
28     RandomListNode copy, copyIter = pseudoHead;
29 
30     while (iter != null) {
31         next = iter.next.next;
32 
33         // extract the copy
34         copy = iter.next;
35         copyIter.next = copy;
36         copyIter = copy;
37 
38         // restore the original list
39         iter.next = next;
40 
41         iter = next;
42     }
43 
44     return pseudoHead.next;
45 }

另外一个，先全部建立新node，再到map中找

https://discuss.leetcode.com/topic/18086/java-o-n-solution

 1 public RandomListNode copyRandomList(RandomListNode head) {
 2   if (head == null) return null;
 3   
 4   Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
 5   
 6   // loop 1. copy all the nodes
 7   RandomListNode node = head;
 8   while (node != null) {
 9     map.put(node, new RandomListNode(node.label));
10     node = node.next;
11   }
12   
13   // loop 2. assign next and random pointers
14   node = head;
15   while (node != null) {
16     map.get(node).next = map.get(node.next);
17     map.get(node).random = map.get(node.random);
18     node = node.next;
19   }
20   
21   return map.get(head);
22 }