平顶山做网站多少钱,西安网站维护,免费个人手机网站,单位门户网站建设的请示深度拷贝一个链表可以分以下几个步骤#xff1a;
步骤 1#xff1a;插入新节点
目标#xff1a;在每个节点后面插入一个复制的节点。步骤#xff1a; 遍历整个链表。对于每个节点 current#xff0c;创建一个新节点 newNode#xff0c;其值为 current.val。将 newNode …
深度拷贝一个链表可以分以下几个步骤
步骤 1插入新节点
目标在每个节点后面插入一个复制的节点。步骤 遍历整个链表。对于每个节点 current创建一个新节点 newNode其值为 current.val。将 newNode 插入到 current 之后。即将 newNode.next 指向 current.next然后将 current.next 指向 newNode。
示例
原链表A - B - C
插入后A - A - B - B - C - C
步骤 2复制随机指针
目标复制每个节点的 random 指针。步骤 再次从头遍历链表。如果 current.random 不为 null则设置 current.next.random 为 current.random.next。
示例
如果 A.random - C则 A.random - C
步骤 3拆分链表
目标将链表分成原链表和复制链表。步骤 初始化两个指针current 指向原链表头copiedHead 指向新链表的头。通过调整 next 指针将链表分离。遍历链表时将 current.next 指向 current.next.next将 copyCurrent.next 指向 copyCurrent.next.next。
示例
分离后
原链表A - B - C新链表A - B - C’
代码如下
class Node{int val;Node next;Node random;public Node(int val){this.val val;this.nextnull;this.randomnull;}
}public class Solution24 {public Node copyRandomList(Node head) {// 长度为n的链表 随即指针random 可以指向链表任意节点或空节点// 构造深拷贝// 你的代码只接受原链表的头节点head为传入参数// 给定一个长度为 n 的链表每个节点都有一个 val 和一个随机指针 random。// 我们的目标是创建一个新的链表该链表是原链表的深拷贝。深拷贝意味着在新链表中创建完全独立的新节点// 其中 next 和 random 指针指向新链表内的节点而不是原链表中的节点。if(head null) return null;// 在每个节点和创建一个新节点Node currenthead;while(current!null){Node newNode new Node(current.val);newNode.next current.next;current.next newNode;current newNode.next;}//复制random指针currenthead;while(current!null){if(current.random!null){current.next.randomcurrent.random.next;}currentcurrent.next.next;}// 拆分链表currenthead;Node copiedHead head.next;Node copyCurrentcopiedHead;while(current!null){current.nextcurrent.next.next;if(copyCurrent.next!null){copyCurrent.nextcopyCurrent.next.next;}currentcurrent.next;copyCurrentcopyCurrent.next;}return copiedHead;}
}
