【LeetCode-中等题】138. 复制带随机指针的链表

题目

解题核心思路：找random指针指向

这里的拷贝属于深拷贝，就是不光是拷贝值，还要拷贝其指针的引用情况。如果只是单独的单向链表，则直接可以根据next指向找到下一个结点，然后创建一个新节点复制过来，直接拷贝，但是题目中的random指针指向的节点是没有归类的，这样我们就不可能使用普通的循环来进行拷贝，因为在拷贝的时候，你只能找到next，但是random并不知道，可能拷贝的同时random都还没创建出来

思路一：哈希

此题的复制，不单单要复制本身的.val值，还要把其next和random指向给复制过来。
那么我们可以借助一个哈希表Map来记录下旧链表的映射关系，key为旧链表的节点（包含next和random指向），value为新建的新节点（val值直接copy旧链表的节点）

1. 建立哈希表，key为旧链表的节点，value为新建的新节点
2. 然后去循环链表的同时，根据key取出新节点，并且（依据旧节点）设置新节点的next和random
3. 最后返回新链表的首节点map.get(head);
   

这里可以用纯哈希+while或者 哈希+递归的方法，原理都是一样的

思路二：迭代构造新链表

给每个旧链表节点后面都连上一个自己的复制节点，然后再根据老节点的random给后面的新节点附上，最后在把就新链表拆出来

1. 构建新老链表结合体
   

2. 更新新节点的random
   

3. 拆链
   

方法一：哈希+递归

 方法一 : 递归+哈希---->用哈希表记录旧值和新值的映射，让新值根据旧值的连接关系，构建新链表Map<Node, Node> map = new HashMap<Node, Node>();public Node copyRandomList(Node head) {if(head==null) return null;if(!map.containsKey(head)){//如果map集合不含head  则创建一份新的head进去  Node newHead = new Node(head.val);map.put(head,newHead);//key--->旧值  value--->新值   //给新值附上 next 和randomnewHead.next = copyRandomList(head.next);newHead.random = copyRandomList(head.random);}return map.get(head);}

方法二：纯哈希

方法二： 纯哈希----->  使用hash存储原结点和克隆结点的映射关系，通过映射关系处理克隆结点的random指针public Node copyRandomList(Node head) {if(head==null) return head;// map方法，空间复杂度O(n)Node oldNode = head;// 使用hash表存储旧结点和新结点的映射Map<Node,Node> map = new HashMap<>();while(oldNode != null){Node newNode = new Node(oldNode.val);map.put(oldNode,newNode);oldNode = oldNode.next;}oldNode = head;//重置 oldNode 位置到head头结点while(oldNode != null){ //根据旧node 映射新nodemap.get(oldNode).next = map.get(oldNode.next);map.get(oldNode).random = map.get(oldNode.random);oldNode = oldNode.next;}return map.get(head);//返回头结点的映射新节点}

方法三：迭代 + 节点拆分

/ 方法三： 迭代 + 节点拆分---->  给每一个旧的链表节点去拼接一个新的到旧节点后面，然后将新结点的random指向旧节点的random指向，最后再把新的节点拆分出来
public Node copyRandomList(Node head) {if (head == null) {return null;}// for (Node node = head; node != null; node = node.next.next) {//     Node nodeNew = new Node(node.val);//     nodeNew.next = node.next;//     node.next = nodeNew;// }// 第一次遍历，拼接新旧链表 旧1-->新1-->旧2--->新2Node node = head;while(node != null){Node nodeNew = new Node(node.val);nodeNew.next = node.next;node.next = nodeNew;node = node.next.next;}// for (Node node = head; node != null; node = node.next.next) {//     Node nodeNew = node.next;//     if(node.random != null) nodeNew.random = node.random.next;//     else nodeNew.random = null;// }// 第二次遍历，给新结点连上旧节点的randomnode = head;// 重置node到head位置while(node != null){Node nodeNew = node.next;if(node.random != null) nodeNew.random = node.random.next; //如果旧节点的random指向null  null本身没有新节点，则直接让新节点的random指向nullelse nodeNew.random = null;node = node.next.next;}Node headNew = head.next;// for (Node node = head; node != null; node = node.next) {//     Node nodeNew = node.next;//     node.next = node.next.next;//     if(nodeNew.next != null) nodeNew.next = nodeNew.next.next;//     else nodeNew.next = null;// }node = head;// 重置node到head位置// 第三次遍历，拆分新链表出来while(node != null){Node nodeNew = node.next;node.next = nodeNew.next;if(nodeNew.next != null) nodeNew.next = nodeNew.next.next;else nodeNew.next = null;//防止最后一个新链表nodeNew.next.next出现空指针node = node.next;}return headNew;}