苏州做企业网站公司,陕西公司网站建设,做采集网站赚钱吗,vue做电商网站解决一#xff1a;回溯 哈希表
本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表#xff0c;我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在#xff0c;当我们拷贝节点时#xff0c;「当前节点的随机指针指向的节点」可能还没创建#xf…解决一回溯 哈希表
本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在当我们拷贝节点时「当前节点的随机指针指向的节点」可能还没创建因此我们需要变换思路。一个可行方案是我们利用回溯的方式让每个节点的拷贝操作相互独立。对于当前节点我们首先要进行拷贝然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝拷贝完成后将创建的新节点的指针返回即可完成当前节点的两指针的赋值。
具体地我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建我们都立刻递归地进行创建。当我们拷贝完成回溯到当前层时我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向因此我们可能递归地多次尝试拷贝某个节点为了防止重复拷贝我们需要首先检查当前节点是否被拷贝过如果已经拷贝过我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。
/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val val;this.next null;this.random null;}
}
*/class Solution {// 旧的node,新的nodeMapNode,Node newNodeMap new HashMap(); public Node copyRandomList(Node head) {if(head null){return null;}if(!newNodeMap.containsKey(head)){// 有旧node但是没有新nodeNode newNode new Node(head.val); // 注意上述构造函数newNodeMap.put(head, newNode); // 要放在两个copyRandomList之上否则后面会连续创建最终导致栈溢出newNode.next copyRandomList(head.next);newNode.random copyRandomList(head.random);}// return newNode;不可以这是一个临时变量return newNodeMap.get(head);}
}注意
要return newNodeMap.get(head);不可以return newNode;因为这是一个这是一个临时变量。newNodeMap.put(head, newNode);要放在两个copyRandomList之上否则后面会连续创建最终导致栈溢出且后面的复制是地址赋值就算先put了也会影响已经put的元素
