您的位置:首页 > 科技 > IT业 > 企业管理咨询服务机构_建筑工程承包方式_德州seo整站优化_百度网盘下载

企业管理咨询服务机构_建筑工程承包方式_德州seo整站优化_百度网盘下载

2024/12/23 7:09:30 来源:https://blog.csdn.net/m0_46290969/article/details/142379190  浏览:    关键词:企业管理咨询服务机构_建筑工程承包方式_德州seo整站优化_百度网盘下载
企业管理咨询服务机构_建筑工程承包方式_德州seo整站优化_百度网盘下载

深度拷贝一个链表可以分以下几个步骤:

步骤 1:插入新节点
  • 目标:在每个节点后面插入一个复制的节点。
  • 步骤
    1. 遍历整个链表。
    2. 对于每个节点 current,创建一个新节点 newNode,其值为 current.val
    3. 将 newNode 插入到 current 之后。即将 newNode.next 指向 current.next,然后将 current.next 指向 newNode

示例

原链表:A -> B -> C

插入后:A -> A' -> B -> B' -> C -> C'

步骤 2:复制随机指针
  • 目标:复制每个节点的 random 指针。
  • 步骤
    1. 再次从头遍历链表。
    2. 如果 current.random 不为 null,则设置 current.next.random 为 current.random.next

示例

如果 A.random -> C,则 A'.random -> C'

步骤 3:拆分链表
  • 目标:将链表分成原链表和复制链表。
  • 步骤
    1. 初始化两个指针:current 指向原链表头,copiedHead 指向新链表的头。
    2. 通过调整 next 指针,将链表分离。
    3. 遍历链表时,将 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.next=null;this.random=null;}
}public class Solution24 {public Node copyRandomList(Node head) {// 长度为n的链表 随即指针random 可以指向链表任意节点或空节点// 构造深拷贝// 你的代码只接受原链表的头节点head为传入参数// 给定一个长度为 n 的链表,每个节点都有一个 val 和一个随机指针 random。// 我们的目标是创建一个新的链表,该链表是原链表的深拷贝。深拷贝意味着在新链表中创建完全独立的新节点,// 其中 next 和 random 指针指向新链表内的节点,而不是原链表中的节点。if(head == null) return null;// 在每个节点和创建一个新节点Node current=head;while(current!=null){Node newNode = new Node(current.val);newNode.next = current.next;current.next = newNode;current = newNode.next;}//复制random指针current=head;while(current!=null){if(current.random!=null){current.next.random=current.random.next;}current=current.next.next;}// 拆分链表current=head;Node copiedHead= head.next;Node copyCurrent=copiedHead;while(current!=null){current.next=current.next.next;if(copyCurrent.next!=null){copyCurrent.next=copyCurrent.next.next;}current=current.next;copyCurrent=copyCurrent.next;}return  copiedHead;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com