东南亚购物网站排名,重庆建设工程安全管理网查询,视频wordpress,上海外贸网站建【问题描述】[中等] 【解答思路】
1. 暴力 直接复制
将链表从头节点一个一个复制下去#xff0c; 在根据记录的总长度num#xff0c;遍历原来的每个节点的random到尾节点个数count#xff0c;然后顺序遍历找到新链表的该指针在num-count上 。 时间复杂度#xff1a;O(N^2…【问题描述】[中等] 【解答思路】
1. 暴力 直接复制
将链表从头节点一个一个复制下去 在根据记录的总长度num遍历原来的每个节点的random到尾节点个数count然后顺序遍历找到新链表的该指针在num-count上 。 时间复杂度O(N^2) 空间复杂度O(N)
class Solution {public Node copyRandomList(Node head) {if(headnull) return head;Node newHeadnew Node(head.val);Node keepnewHead;Node nodehead.next;int num1;//记录节点数while(node!null){keep.nextnew Node(node.val);nodenode.next;keepkeep.next;num;}keep.nextnull;Node newnnewHead;Node oldnhead;//n r 定位randomNode n;Node r;int count;while (oldn!null){n oldn.random;//进行循环找到酒链表random指向的位置nrnewHead;count0;//计算出旧链表n距离尾节点个数while (n!null){nn.next;count;}//计算旧的random在链表中的位置 利用新旧链表新旧位置相同的原理for(int resnum-count;res0;res--){rr.next;}newn.randomr;//遍历新旧链表oldnoldn.next;newnnewn.next;}return newHead;}
}作者zhao-1z
链接https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/javaliang-chong-xie-fa-by-zhao-1z/
2. HashMap O(N)空间 **时间复杂度O(N) 空间复杂度O(N) **
/*
// Definition for a Node.
class Node {public int val;public Node next;public Node random;public Node() {}public Node(int _val,Node _next,Node _random) {val _val;next _next;random _random;}
};
*/
public class Solution {// Visited dictionary to hold old node reference as key and new node reference as the valueHashMapNode, Node visited new HashMapNode, Node();public Node getClonedNode(Node node) {// If the node exists thenif (node ! null) {// Check if the node is in the visited dictionaryif (this.visited.containsKey(node)) {// If its in the visited dictionary then return the new node reference from the dictionaryreturn this.visited.get(node);} else {// Otherwise create a new node, add to the dictionary and return itthis.visited.put(node, new Node(node.val, null, null));return this.visited.get(node);}}return null;}public Node copyRandomList(Node head) {if (head null) {return null;}Node oldNode head;// Creating the new head node.Node newNode new Node(oldNode.val);this.visited.put(oldNode, newNode);// Iterate on the linked list until all nodes are cloned.while (oldNode ! null) {// Get the clones of the nodes referenced by random and next pointers.newNode.random this.getClonedNode(oldNode.random);newNode.next this.getClonedNode(oldNode.next);// Move one step ahead in the linked list.oldNode oldNode.next;newNode newNode.next;}return this.visited.get(head);}
}作者LeetCode
链接https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/
3. HashMap O(N)空间
遍历第一遍链表我们不考虑链表之间的相互关系仅仅生成所有节点然后把它存到 HashMap 中hval 作为 keyNode 作为 value。
遍历第二遍链表将之前生成的节点取出来更新它们的 next 和 random 指针。
时间复杂度O(N) 空间复杂度O(N)
public Node copyRandomList(Node head) {if (head null) {return null;}HashMapNode, Node map new HashMap();Node h head;while (h ! null) {Node t new Node(h.val); map.put(h, t);h h.next;}h head;while (h ! null) {if (h.next ! null) {map.get(h).next map.get(h.next);}if (h.random ! null) {map.get(h).random map.get(h.random);}h h.next;}return map.get(head);
}作者windliang
链接https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-32/
4. HashMap O(N)空间
只遍历一次链表。 核心思想就是延迟更新它的 next。 1 - 2 - 3 用 cur 指向已经生成的节点的末尾 1 - 2 ^ c 然后将 3 构造完成 最后将 2 的 next 指向 3 1 - 2 - 3 ^ c 期间已经生成的节点存到 HashMap 中第二次遇到的时候直接从 HashMap 中拿 时间复杂度O(N) 空间复杂度O(N)
public Node copyRandomList(Node head) {if (head null) {return null;}HashMapNode, Node map new HashMap();Node h head;Node cur new Node(-1); //空结点dummy 节点为了方便头结点计算while (h ! null) {//判断当前节点是否已经产生过if (!map.containsKey(h)) {Node t new Node(h.val);map.put(h, t);}//得到当前节点去更新它的 random 指针Node next map.get(h);if (h.random ! null) {//判断当前节点是否已经产生过if (!map.containsKey(h.random)) {next.random new Node(h.random.val);map.put(h.random, next.random);} else {next.random map.get(h.random);}}//将当前生成的节点接到 cur 的后边cur.next next;cur cur.next;h h.next;}return map.get(head);
}
5. O(1)空间 (用原链表的 next 域保存新生成的节点)
主要解决的问题就是我们生成节点以后当更新它的 random 的时候怎么找到之前生成的节点前两种解法用了 HashMap 全部存起来这里的话可以利用原来的链表的指针域。
主要需要三步。
生成所有的节点并且分别插入到原有节点的后边更新插入节点的 random将新旧节点分离开来
时间复杂度O(N) 空间复杂度O(1)
public Node copyRandomList(Node head) {if (head null) {return null;}Node l1 head;Node l2 null;//生成所有的节点并且分别插入到原有节点的后边while (l1 ! null) {l2 new Node(l1.val);l2.next l1.next;l1.next l2;l1 l1.next.next;}//更新插入节点的 randoml1 head;while (l1 ! null) {if (l1.random ! null) {l1.next.random l1.random.next;}l1 l1.next.next;}l1 head;Node l2_head l1.next;//将新旧节点分离开来while (l1 ! null) {l2 l1.next;l1.next l2.next;if (l2.next ! null) {l2.next l2.next.next;}l1 l1.next;}return l2_head;
}
/*
// Definition for a Node.
class Node {public int val;public Node next;public Node random;public Node() {}public Node(int _val,Node _next,Node _random) {val _val;next _next;random _random;}
};
*/
public class Solution {public Node copyRandomList(Node head) {if (head null) {return null;}// Creating a new weaved list of original and copied nodes.Node ptr head;while (ptr ! null) {// Cloned nodeNode newNode new Node(ptr.val);// Inserting the cloned node just next to the original node.// If A-B-C is the original linked list,// Linked list after weaving cloned nodes would be A-A-B-B-C-CnewNode.next ptr.next;ptr.next newNode;ptr newNode.next;}ptr head;// Now link the random pointers of the new nodes created.// Iterate the newly created list and use the original nodes random pointers,// to assign references to random pointers for cloned nodes.while (ptr ! null) {ptr.next.random (ptr.random ! null) ? ptr.random.next : null;ptr ptr.next.next;}// Unweave the linked list to get back the original linked list and the cloned list.// i.e. A-A-B-B-C-C would be broken to A-B-C and A-B-CNode ptr_old_list head; // A-B-CNode ptr_new_list head.next; // A-B-CNode head_old head.next;while (ptr_old_list ! null) {ptr_old_list.next ptr_old_list.next.next;ptr_new_list.next (ptr_new_list.next ! null) ? ptr_new_list.next.next : null;ptr_old_list ptr_old_list.next;ptr_new_list ptr_new_list.next;}return head_old;}
}
6. O(1)空间 (用原链表的 random域保存新生成的节点)
可以利用原链表的 random 域把新生成的节点保存起来。 主要还是三个步骤。
生成所有的节点将它们保存到原链表的 random 域同时利用新生成的节点的 next 域保存原链表的 random。更新新生成节点的 random 指针。恢复原链表的 random 指针同时更新新生成节点的 next 指针。
时间复杂度O(N) 空间复杂度O(1)
public Node copyRandomList(Node head) {if (head null) {return null;}Node l1 head;Node l2 null;//生成所有的节点讲它们保存到原链表的 random 域//同时利用新生成的节点的 next 域保存原链表的 random。while (l1 ! null) {l2 new Node(l1.val);l2.next l1.random;l1.random l2;l1 l1.next;}l1 head;//更新新生成节点的 random 指针。while (l1 ! null) {l2 l1.random;l2.random l2.next ! null ? l2.next.random : null;l1 l1.next;}l1 head;Node l2_head l1.random;//恢复原链表的 random 指针同时更新新生成节点的 next 指针。while (l1 ! null) {l2 l1.random;l1.random l2.next;l2.next l1.next ! null ? l1.next.random : null;l1 l1.next;}return l2_head;
}
【总结】
1.思路1暴力ON^2- 思路2.3.4 HashMap O(N)-思路5.6 复制链表O1
2.链表操作的核心思想就是在改变某一个节点的指针域的时候一定要把该节点的指针指向的节点用另一个指针保存起来以免造成丢失。
3.链表 画图
转载链接https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-32/ 转载链接https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-32/
