算法-深度拷贝链表（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;
    }
}