LeetCode138:Copyalinkedlistwithrandompointershttps://leetcode-cn.com/probl...1.题目描述给你一个长度为n的链表，每个节点包含a附加一个随机指针random，可以指向链表中的任意节点或空节点。构造此链表的深层副本。一个深拷贝应该恰好包含n个全新的节点，其中每个新节点的值被设置为其对应的原始节点的值。新节点的next指针和随机指针也应该指向复制链表中的新节点，这样原链表和复制链表中的这些指针就可以表示相同的链表状态。复制链表中的指针不应指向原链表中的节点。例如，如果原始链表中有两个节点X和Y，其中X.random-->Y。那么复制链表中对应的两个节点x和y也有x.random-->y。返回复制列表的头节点。输入/输出中的链表由n个节点的链表表示。每个节点由一个[val,random_index]表示：val：表示Node.val的整数。random_index：随机指针指向的节点的索引（取值范围为0到n-1）；如果它不指向任何节点，则为null。你的代码只接受原链表的头节点head作为传入参数。节点定义：classNode{intval;下一个节点；节点随机；公共节点（intval）{this.val=val;这个.下一个=空；this.random=null;}}2.输入示例：head=[[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]3.附加空间复杂度为O(1)的思路1.原链表的每个节点之后，复制一个新节点并将其连接到旧节点：复制前：1->2->3，复制后：1->1\`->2->2\`->3->3\`2，原节点随机指针的关系，在新节点上做一个副本3.将新旧节点分开，额外空间复杂度为O(N)1.使用Map存储新旧节点，Key：oldnode,Value:newnode2.构造老节点对应的新节点3.调整新节点的next指针，调整新节点的随机指针4.源码的额外空间复杂度为O(1)/***@authorJava与算法学习：周一*/publicNodecopyRandomList(Nodehead){if(head==null){returnnull;}//1.在旧节点后面插入新节点//调整前：1->2->3->null，调整后：1->1`->2->2`->3->3`->空节点current=head;下一个节点=空；while(current!=null){//标记当前节点在原链表中的下一个节点next=current.next;//在原链表的当前节点后面插入一个新节点current.next=newNode(current.值）；//调整新插入节点的下一个节点current.next.next=next;//向后移动当前节点current=next;}//2.调整新插入节点的随机指针Nodecopy=null;当前=头部；while(current!=null){//新节点copy=current.next;//标记当前节点在原链表中的下一个节点next=current.next.next;//调整新节点的随机节点co.和rcurrent.random!=null？当前.随机.下一个：空；//向后移动当前节点current=next;}//3.分离新旧节点current=head;//记录新链表的头节点Noderes=head.next;while(current!=null){//新节点copy=current.next;//标记当前节点在原链表中的下一个节点next=current.next.next;//当前节点的下一个节点指向原链表当前节点的下一个节点在当前节点（即调回旧节点的引用）current.next=next;//新节点的下一个节点指向原链表中当前节点下一个节点的下一个节点（即提取新节点的引用）copy.next=next!=null?下一个下一个：空；//向后移动当前节点current=next;@authorJava和算法Xi:Monday*/publicNodecopyRandomListByMap(Nodehead){//键：旧节点，值：新节点HashMap
