138.随机链表的复制

题目:138.随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

• 示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

• 示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

• 示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

• 提示：

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random 为 null 或指向链表中的节点。

思路

要构造一个具有随机指针的链表的深拷贝，可以使用以下的算法思路：

1. 第一步: 在每个原链表节点后面创建一个新节点。新节点的值与原节点相同，新节点的next指针指向原节点的下一个节点。这样，链表将会变成原节点和对应的新节点交替的形式。比如下图中原节点 1 不再指向原原节点 2，而是指向新节点 1。
   

2. 第二步: 更新新节点的random指针。对于每个新节点newNode，它的random指针应该指向原节点random指向的那个节点的副本，即 current.next.random = current.random.next;。
   

3. 第三步: 将交替的链表拆分成两个独立的链表，即原链表和深拷贝的链表。
   

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public Node copyRandomList(Node head) {
    Node result = new Node(0);
    Node resultCurrent = result;
    // 1. 在原链表的每个节点后面创建一个新节点
    Node current = head;
    while (current != null) {
        Node newNode = new Node(current.val);
        newNode.next = current.next;
        current.next = newNode;
        current = newNode.next;
    }
    // 2. 设置新节点的 random 指针
    current = head;
    while (current != null) {
        if (current.random != null) {
            current.next.random = current.random.next;
        }
        current = current.next.next;
    }
    // 3. 拆分链表，得到原链表和复制后的链表
    current = head;
    while (current != null) {
        resultCurrent.next = current.next;
        current.next = current.next.next;
        resultCurrent = resultCurrent.next;
        current = current.next;
    }
    return head;
}