目录
随机链表的复制
1. 完整题目
2.错误做法
3.第一次遍历
1.拷贝所有旧节点的val域
2. 串联老节点和新节点
3. 第一次遍历代码：
4.第二次遍历
1. 表示出新链表的节点
2. 表示出新节点的next,random
3. 通过映射关系赋值next,random
4. 第二次遍历代码
5.设置返回值
6.完整代码
随机链表的复制
随机链表的复制 - 力扣（LeetCode）
1. 完整题目
进一步读题，获取更多信息：
我们通过进一步读题，可以得出每个节点的形式，每个节点有三个域：val域，next域，及random域。通过节点的形式，我们可以画出一条符合题意的链表。
这条链表入下图，val域存储着该节点存放的值；next域存放着下一个节点的地址；
random域比较特殊;它可能存放着链表中，任意节点的地址，可以是指向自己，也可以指向不相邻的节点，甚至可以为null。也就是说，random域存放着链表中任意一个节点的指针或者为null。
我们要对这条链表进行深拷贝，就是将这条链表中所有节点的val域，及各个节点间域的指向关系，都以相同形式拷贝出一条新链表。
2.错误做法
对于该题，很多uu们的做法是：定义一个cur，用cur从当前链表的头节点开始，遍历链表，把遍历到的的节点的cur.val，cur.next，cur.random三个域，拷贝到新创建的链表中，直到cur遍历完完整的链表。
这种做法是错误的，为什么呢？
题目的意思是，让我们对原链表进行深拷贝。
对于图中的原链表，当前cur指向该链表的头节点，cur.next指向0x56这个节点，要把0x56拷贝一份，那拷贝出来的节点的地址可能是0x89。
这时候就出现问题了，按照这种做法，拷贝出的新的头节点的next域，指向的是原链表的第二个节点，而不是指向新链表的第二个节点。
3.第一次遍历
1.拷贝所有旧节点的val域
对于该题，我们定义一个cur，遍历原链表的每一个节点。
cur从头节点开始向后遍历，只要cur不为null，就对应地实例化一个新的节点。
实例化好新节点后，可以先不管新节点的next域和random域，把旧节点的val值拷贝到新节点。
2. 串联老节点和新节点
在拷贝所有旧节点的val域的同时，我们需要提前创建好一个HashMap类型的map，map中的每一个元素entry，key域用于存储旧节点的地址，val域用于存储新节点的地址。通过map的特性，我们就把每一个老节点和对应的新节点串联起来：
当然，仅仅一次遍历，是完全不足以解决问题的，我们还要进行第二次遍历，题目中传入的形参head，指向原链表头节点。方便每次遍历时，cur都能直接找到原链表头节点：
3. 第一次遍历代码：
4.第二次遍历
第二次遍历，就是要通过刚刚串联旧节点和新节点的map，修改新节点的next域和random域
1. 表示出新链表的节点
对于新链表的节点地址，我们只要拿到了元素entry的key值，通过map，就可以通过get()方法，来获取到entry元素对应key的val值，entry.val==map.get(entry.key)。
2. 表示出新节点的next,random
对于新节点的next域，可以表示为map.get(cur).next。
同理，对于新节点的random域，可以表示为map.get(cur).random。
3. 通过映射关系赋值next,random
就拿新旧节点的next域来举例，我们可以通过cur.next指向旧链表的下一个节点，那么如何通过串联新旧节点的map，来让新节点的next域，指向新链表中的下一个节点呢？
通过map.get(cur.next)：
cur.next拿到了 原链表正在遍历的节点 的下一个节点 ；
map.get(~)拿到了 对应新链表的节点 的地址。
通过map.get(cur).next：
map.get(cur)拿到了 原链表正在遍历的节点 对应新链表的节点；
~.next 拿到了 对应新链表的节点 的next域。
所以，令 map.get(cur).next = map.get(cur.next) 即可正确地修改新节点的next域，指向新链表的下一个节点。
修改新节点的random域同理，map.get(cur).random = map.get(cur.random).
4. 第二次遍历代码
5.设置返回值
以上，就是随机链表复制的全部内容 ！
6.完整代码
class Node{
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
public Node copyRandomList(Node head) {
HashMap<Node,Node> map=new HashMap<>();
Node cur=head;
while (cur!=null){
Node node=new Node(cur.val);
map.put(cur,node);
cur=cur.next;
}
cur=head;
while (cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
public List<String> topKFrequent(String[] words , int k){
HashMap<String,Integer> map=new HashMap<>();
for (String word : words) {
if (map.get(word)==null){
map.put(word,1);
} else {
int val = map.get(word);
map.put(word,val+1);
}
}
