题目
解题核心思路:找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
文章来源:https://www.toymoban.com/news/detail-684129.html -
拆链
文章来源地址https://www.toymoban.com/news/detail-684129.html
方法一:哈希+递归
方法一 : 递归+哈希---->用哈希表记录旧值和新值的映射,让新值根据旧值的连接关系,构建新链表
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;
}
到了这里,关于【LeetCode-中等题】138. 复制带随机指针的链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!