题目
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
程序核心思想
- 这个题目用的数据结构为hashmap。把原始数据的节点看做键，把复制的节点看做值，这样就是一个键值对，然后存入hashmap中，这一步只进行值的复制。
然后遍历原始链表，遍历一个节点，就可以拿到这个节点对应的下个节点和随机节点，然后把这两个节点和遍历的当前节点看做是键，就可以从hashmap中取出它们对应的复制节点，然后让遍历的节点的复制的next和random指针，分别指向它们的复制节点即可。 - 第二个解法是不需要使用hashmap的方法。从第一个方法可以看出，hashmap的作用是记录一个节点的复制节点在哪里，所以这一个解法就用了结构来解决这个问题。它把每个节点的拷贝节点放到了源节点的后面，也就是源节点的next指针指向了拷贝节点，然后就处理random指针，源节点的random的指针指向的节点的下一个节点，就是它的拷贝节点的random指针应该指向的节点。最后就是处理原链表和拷贝链表的分开问题，非常简单，不多说了。
在LeetCode中，第一种方法和第二种方法使用的内存是差不多的，但是第二种方法比第一种方法快了一倍。
Tips
HashMap的使用：
添加元素——put()
通过键获取值 —— get()
是否为空 ——isEmpty()
是否包含某个键 —— containsKey()
是否包含某个值 ——containsValue
删除key下的value ——remove(key)
删除一个键值对 ——remove(key, value)
键值对的个数 ——size()
代码
import java.util.HashMap;
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead == null) return null;
HashMap<RandomListNode, RandomListNode> hm = new HashMap<RandomListNode, RandomListNode>();
RandomListNode start = pHead;
while(start != null){
hm.put(start, new RandomListNode(start.label));
start = start.next;
}
start = pHead;
while(start != null){
hm.get(start).next = hm.get(start.next);
hm.get(start).random = hm.get(start.random);
start = start.next;
}
return hm.get(pHead);
}
}
//LeetCode
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node a = head;
Node b = null;
Node c = null;
if(a.next != null){
b = a.next;
}else{
if(a.random == a){
Node node = new Node(a.val, null, null);
node.random = node;
return node;
}else{
return new Node(a.val, null, null);
}
}
while(b != null){
a.next = new Node(a.val, b, null);
a = b;
b = b.next;
}
a.next = new Node(a.val, b, null);
a = head;
while(a != null && a.next != null && a.next.next != null){
if(a.random != null){
a.next.random = a.random.next;
}else{
a.next.random = null;
}
a = a.next.next;
}
if(a.random != null){
a.next.random = a.random.next;
}else{
a.next.random = null;
}
a = head;
b = a.next;
c = b;
while(b.next != null){
a.next = b.next;
a = a.next;
b.next = a.next;
b = b.next;
}
a.next = null;
b.next = null;
return c;
}
}
