宁波网站排名优化seo,上海公司网站建设公司,汕头网站seo外包,国外优秀网站文章目录题目描述思路 代码1. 哈希表法2. 原地算法二刷题目描述
主要有两个考虑点#xff1a; 不能改变原链表新链表赋予 next、random 时#xff0c;复制结点不一定存在 思路 代码
1. 哈希表法
O(n)、O(n)参考了dalao的写法#xff0c;这里哈希表…
文章目录题目描述思路 代码1. 哈希表法2. 原地算法二刷题目描述
主要有两个考虑点 不能改变原链表新链表赋予 next、random 时复制结点不一定存在 思路 代码
1. 哈希表法
O(n)、O(n)参考了dalao的写法这里哈希表用得非常巧妙值得学习思路在哈希表中建立 Node - CopyNode 的联系在此基础上进行 next random 的处理即可。
/*
// 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 {public Node copyRandomList(Node head) {if(head null) {return null;}// 哈希表做法Node - CopyNodeMapNode, Node hashmap new HashMap();for(Node temp head; temp ! null; temp temp.next) {hashmap.put(temp, new Node(temp.val));}for(Node temp head; temp ! null; temp temp.next) {// next 的处理hashmap.get(temp).next hashmap.get(temp.next);// random 的处理hashmap.get(temp).random hashmap.get(temp.random);}return hashmap.get(head);}
}2. 原地算法
O(n)、O(1)相对于方法1此处不需要占用额外空间注意原链表的恢复、边界结点的处理
class Solution {public Node copyRandomList(Node head) {if(head null) {return null;}// 原地算法// 1. 首先 1 - 2 - 3 变成 1 - 1* - 2 - 2* - 3 - 3*for(Node temp head; temp ! null; temp temp.next.next) {Node copy new Node(temp.val);copy.next temp.next;temp.next copy;}// 2. 进行 random 的处理for(Node temp head; temp ! null; temp temp.next.next) {if(temp.random ! null) {temp.next.random temp.random.next;}}// 3. 分开 1 - 1* - 2 - 2* - 3 - 3* 变成 1* - 2* - 3*Node copyHead head.next;for(Node temp head; temp ! null; temp temp.next) {// 取到原本的正确nextNode nextNode temp.next.next;// * - *if(nextNode ! null) {temp.next.next temp.next.next.next;}// 1 - 2temp.next nextNode;}return copyHead;}
}二刷
哈希表
class Solution {public Node copyRandomList(Node head) {MapNode, Node map new HashMap();for(Node temp head; temp ! null; temp temp.next) {map.put(temp, new Node(temp.val));}for(Node temp head; temp ! null; temp temp.next) {map.get(temp).next map.get(temp.next);map.get(temp).random map.get(temp.random);}return map.get(head);}
}原地算法二刷来看还是很有含金量的做法思路
class Solution {public Node copyRandomList(Node head) {if(head null) return null;for(Node temp head; temp ! null; temp temp.next.next) {Node newNode new Node(temp.val);newNode.next temp.next;temp.next newNode;}for(Node temp head; temp ! null; temp temp.next.next) {temp.next.random temp.random null ? null : temp.random.next;}Node ans head.next;for(Node temp head; temp ! null; temp temp.next) {Node tempNode temp.next;temp.next temp.next.next;tempNode.next temp.next null ? null : tempNode.next.next;}return ans;}
}
