文章目录
- 题目
- 解题核心思路：找random指针指向
- 思路一：哈希
- 思路二：迭代构造新链表
- 方法一：哈希+递归
- 方法二：纯哈希
- 方法三：迭代 + 节点拆分
题目
解题核心思路：找random指针指向
这里的拷贝属于深拷贝，就是不光是拷贝值，还要拷贝其指针的引用情况。如果只是单独的单向链表，则直接可以根据next指向找到下一个结点，然后创建一个新节点复制过来，直接拷贝，但是题目中的random指针指向的节点是没有归类的，这样我们就不可能使用普通的循环来进行拷贝，因为在拷贝的时候，你只能找到next，但是random并不知道，可能拷贝的同时random都还没创建出来
思路一：哈希
此题的复制，不单单要复制本身的.val值，还要把其next和random指向给复制过来。
那么我们可以借助一个哈希表Map来记录下旧链表的映射关系，key为旧链表的节点（包含next和random指向），value为新建的新节点（val值直接copy旧链表的节点）
- 建立哈希表，key为旧链表的节点，value为新建的新节点
- 然后去循环链表的同时，根据key取出新节点，并且（依据旧节点）设置新节点的next和random
- 最后返回新链表的首节点map.get(head);
这里可以用纯哈希+while或者 哈希+递归的方法，原理都是一样的
思路二：迭代构造新链表
给每个旧链表节点后面都连上一个自己的复制节点，然后再根据老节点的random给后面的新节点附上，最后在把就新链表拆出来
-
构建新老链表结合体
-
更新新节点的random
-
拆链
方法一：哈希+递归
方法一 : 递归+哈希---->用哈希表记录旧值和新值的映射，让新值根据旧值的连接关系，构建新链表
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 和random
newHead.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 映射新node
map.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--->新2
Node 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;
// }
// 第二次遍历，给新结点连上旧节点的random
node = head;// 重置node到head位置
while(node != null){
Node nodeNew = node.next;
if(node.random != null) nodeNew.random = node.random.next;
//如果旧节点的random指向null null本身没有新节点，则直接让新节点的random指向null
else 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;
}
