网站建设报价单 非常好用的报价模板.doc,福州做网站fjfzwl,金山西安网站建设,seo网络营销技术**138.**给你一个长度为 n 的链表#xff0c;每个节点包含一个额外增加的随机指针 random #xff0c;该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成#xff0c;其中每个新节点的值都设为其对应的原节点的值。新节… **138.**给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示 val一个表示 Node.val 的整数。 random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。 示例 1 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2 输入head [[1,1],[2,1]] 输出[[1,1],[2,1]] 示例 3 输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]] /*// 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;}}*/我的原始人解法先遍历一遍链表复制出没有 random 的链表与此同时记录下每个原结点对应的复制节点。第二轮遍历的时候复制 random 即可 public Node copyRandomList(Node head) {MapNode,Node map new HashMap();// 头部加了一个哑结点Node node new Node(-1);Node temp node;Node tempHead head;while(head!null){node.next new Node(head.val);map.put(head,node.next);headhead.next;nodenode.next;}head tempHead;node temp;while(head!null){Node random map.get(head.random);node.next.random random;headhead.next;nodenode.next;}return temp.next;}或者可以像他人题解先只是创建每个节点第二轮遍历的时候直接在 map 中把节点连起来创建链表 public Node copyRandomList(Node head) {if(head null) return null;Node cur head;MapNode, Node map new HashMap();// 3. 复制各节点并建立 “原节点 - 新节点” 的 Map 映射while(cur ! null) {map.put(cur, new Node(cur.val));cur cur.next;}cur head;// 4. 构建新链表的 next 和 random 指向while(cur ! null) {map.get(cur).next map.get(cur.next);map.get(cur).random map.get(cur.random);cur cur.next;}// 5. 返回新链表的头节点return map.get(head);}还有个巧妙的思路构建一个新的拼接链表为原节点1 - 新节点1 - 原节点2 - 新节点1 -…。然后你只需要遍历这个链表新结点的 next 就为该节点的 next 的 next新结点的 random 就为原结点的 random 的 next。其实这也是一种原节点对应新节点的形式只不过在 map 中表现为 key-val在这里表现为 node - node.next。 public Node copyRandomList(Node head) {if(head null){return null;}// 暂存头结点待会用来重新遍历Node tempHead head;// 拼接新链表while(head ! null){Node node new Node(head.val);node.next head.next;head.next node;head node.next;}// 头结点复原再遍历一遍构建新链表 random 的指向head tempHead;while(head ! null){if(head.random ! null){head.next.random head.random.next;}head head.next.next;}// 头结点再复原最后遍历一遍拆分出原链表和结果链表head tempHead;// 最后结果的头结点下面用来遍历Node ans head.next;// 暂存最后结果的头结点Node tempAns ans;// 构建到尾结点就不构建了所以是 ans.next ! null也没 next 让你继续构建了while(ans.next ! null){// 或者 head.next head.next.nexthead.next ans.next;head head.next;ans.next head.next;ans ans.next;}// 原链表尾结点复原head.next null;return tempAns;}
