解题思路1：
一个深度的 copy。
1，如果只有next，那就好办了，一个挨着一个的copy就好
2，这里有random，最理想的就是 random指哪儿，我们就知道那里对应的copy在哪儿。 这个对应，就是map，立刻想到的就是hashmap
/**
* 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 {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return head;
Map<RandomListNode, RandomListNode> mapper = new HashMap<>();
RandomListNode it = head;
while(it != null){
mapper.put(it, new RandomListNode(it.label) );
it = it.next;
}
it = head;
while(it != null){
RandomListNode copy = mapper.get(it);
copy.next = mapper.get(it.next);
copy.random = mapper.get(it.random);
it = it.next;
}
return mapper.get(head);
}
}
解题思路2:
1，这里参考网上的方法，直接把copy放在原node的后面，最后再拆链。
总体来看，也是为了 找到 random指向的copy。
2，注意一点，random pointer是可以指向 null的。如果面试官没有说，你也要问。
上面的解法中，hashMap.get(it.random)不用考虑这个问题，因为 hashMap.get(null) 返回还是null
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return head;
RandomListNode it = head;
while(it != null){
RandomListNode copy = new RandomListNode(it.label);
copy.next = it.next;
it.next = copy;
it = copy.next;
}
it = head;
while( it != null){
RandomListNode copy = it.next;
copy.random = (it.random != null) ? it.random.next : null;
it = copy.next;
}
RandomListNode dummy = new RandomListNode(0);
RandomListNode p = dummy;
it = head;
while( it != null ){
RandomListNode copy=it.next;
p.next = copy;
it.next = copy.next;
it = it.next;
p = p.next;
}
return dummy.next;
}
}
