算法-深度拷贝链表（138）

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

步骤 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;}
}