LeetCode题练习与总结：随机链表的复制--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 或指向链表中的节点。

二、解题思路

复制每个节点：遍历原始链表，对于每个节点创建其副本，并将副本插入到原节点和下一个节点之间。比如，原始链表是 A -> B -> C，则变为 A -> A’ -> B -> B’ -> C -> C’，其中 A’, B’, C’ 是对应 A, B, C 的副本。
复制随机指针：再次遍历链表，这次设置每个副本节点的random指针。由于副本节点紧跟在原节点之后，可以通过原节点的random指针找到对应的副本节点。
拆分链表：最后，将原始链表和复制链表分离。保持原链表不变，并返回复制链表的头节点。

三、具体代码

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // Step 1: Copy each node and insert it to the list
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            newNode.next = current.next;
            current.next = newNode;
            current = newNode.next;
        }

        // Step 2: Copy random pointers for each copied node
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // Step 3: Separate the copied list from the original list
        Node dummy = new Node(0);
        Node copy = dummy;
        current = head;
        while (current != null) {
            copy.next = current.next;
            copy = copy.next;
            current.next = copy.next;
            current = current.next;
        }

        return dummy.next;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

复制每个节点：这一步需要遍历整个链表一次，时间复杂度为 O(n)，其中 n 是链表中的节点数。
复制随机指针：这一步同样需要遍历整个链表一次，时间复杂度也是 O(n)。
拆分链表：这一步同样需要遍历整个链表一次，时间复杂度为 O(n)。
综合以上步骤，总的时间复杂度是 O(n) + O(n) + O(n) = O(n)。

2. 空间复杂度

复制每个节点：这一步为每个节点创建了一个新的副本节点，因此需要额外的空间来存储这些节点。由于新节点的数量与原链表的节点数相同，所以空间复杂度为 O(n)。
复制随机指针：这一步没有使用额外的空间，只是修改了节点之间的指针。
拆分链表：这一步也没有使用额外的空间，只是重新排列了节点之间的指针。
综合以上步骤，总的空间复杂度是 O(n)。

这里的时间复杂度和空间复杂度都是基于链表的长度来计算的。时间复杂度是线性的，因为我们只需要遍历链表几次，每次都是线性时间。空间复杂度也是线性的，因为我们创建了一个与原链表长度相同的复制链表。

五、总结知识点

链表操作：代码中涉及了链表的遍历、节点的创建、节点间关系的修改（包括next和random指针）以及链表的拆分。
指针操作：代码中使用了多个指针来遍历和修改链表。例如，current指针用于遍历原始链表，newNode用于创建新节点，copy和dummy用于构建复制链表。
递归与迭代：虽然代码中没有直接使用递归，但它使用了迭代的方式来遍历链表。迭代是处理链表问题的一种常见方法。
边界条件处理：代码中首先检查了链表为空的情况，并进行了相应的处理，这是一种常见的边界条件检查。
链表拼接：在第一步中，代码将新创建的节点插入到原始链表中，这是链表拼接的一种形式。
链表拆分：在第三步中，代码将复制后的链表从原始链表中分离出来，这是链表拆分的一个例子。
虚拟头节点（Dummy Node）的使用：代码中使用了虚拟头节点dummy来简化链表操作，特别是在构建新的链表时。虚拟头节点通常在处理链表问题时非常有用，因为它可以避免处理头节点的特殊情况。
链表深拷贝：整个代码的目的是实现链表的深拷贝，这是一种常见的编程技巧，用于创建一个独立于原始链表的新链表。