企业官网建设流程全解析

网站设计的目的是什么,wordpress 算数验证码,wordpress 添加 联系我们,网站开发和推广方案1.题目要求#xff1a;深拷贝一个链表#xff0c;要求新链表中的每个节点都是新创建的#xff0c;并且这些节点的random指针都指向新链表中的相应节点。2.思路#xff1a;#xff08;1#xff09;如果没有random指针#xff0c;只需要在遍历链表的同时#xff0c;依此复…1.题目要求深拷贝一个链表要求新链表中的每个节点都是新创建的并且这些节点的random指针都指向新链表中的相应节点。2.思路1如果没有random指针只需要在遍历链表的同时依此复制每个节点创建新节点并复制val添加在新链表的末尾。2有random指针拷贝就变得复杂了。需要知道random指向的那个节点在新链表中是哪个节点。3所以必须记录原链表节点到新链表节点的映射map。这样可以通过原链表random指向的节点知道新链表的random应该指向哪个节点。4难道应该使用哈希表吗其实不需要。可以把新链表和旧链表“混在一起”。5举例有一个链表1-2-3依次复制每个节点创建新节点并复制val和next把新节点直接插到原节点的后面形成一个交错链表1-1-2-2-3-3。6此时原链表节点的下一个节点就是其对应的新链表节点了。7然后遍历这个交错链表假如节点1的random指向节点3那么就把节点1的random指向节点3的下一个节点3这样就完成了对random指针的复制。8最后从交错链表中分离出1-2-3即为深拷贝后的链表。注意不能只删除节点123因为题目要求原链表的next不能修改。3.复杂度分析1时间复杂度O(n)其中n是链表的长度。2空间复杂度O(1)返回值不计入。附代码class Solution { public Node copyRandomList(Node head) { if(head null){ return head; } //复制每个节点把新节点直接插到原节点的后面 for(Node cur head;cur ! null;cur cur.next.next){ cur.next new Node(cur.val,cur.next); //创建一个新节点复制原节点的值将新节点的next指向原节点的下一个节点 } //遍历交错链表中的原链表节点 for(Node cur head;cur ! null;cur cur.next.next){ if(cur.random ! null){ //要复制的random是cur.random的下一个节点 //cur表示每一个原节点 //cur.next表示每一个复制节点 //cur.next.random表示每一个复制节点的random指针 //cur.random表示每一个原节点的random指针 //cur.random.next表示每一个原节点的random指针的下一个节点即原节点的的random指针指向节点的对应复制节点 cur.next.random cur.random.next; } } //把交错链表分离成两个链表 Node newHead head.next; //新链表的头是原链表头的复制节点 Node cur head; //表示当前处理的原节点 //cur在循环外声明是为了保证后面循环结束后仍可以访问cur for(;cur.next.next ! null;cur cur.next){ //当cur后面至少有两个节点时继续循环因为要保证当前原节点有复制节点和下一个原节点 Node copy cur.next; //用copy表示当前复制节点 cur.next copy.next; //原节点指向下一个原节点 copy.next copy.next.next; //复制节点指向下一个复制节点 } // cur.next.next null时循环结束此时cur指向最后一个原节点 cur.next null; //恢复最后一个原节点的指针指向最后一个原节点应该指向null return newHead; } }