构造 LinkedList 的深层复制

一. 问题描述

给定一个链表，其中每个节点包含一个额外的随机指针，这个指针可以指向链表中的任何节点或为 null。我们的目标是创建一个链表的深度复制。

示例

原始链表

Node1(val=1) -> Node2(val=2) -> Node3(val=3)

带随机指针

• Node1.random: Node3
• Node2.random: Node1
• Node3.random: Node2

新链表

NewNode1(val=1) -> NewNode2(val=2) -> NewNode3(val=3)

带随机指针

• NewNode1.random: NewNode3
• NewNode2.random: NewNode1
• NewNode3.random: NewNode2

二. 代码实现

以下是实现深度复制的代码：

public Node CopyRandomList(Node head)
{
    // 如果链表为空，直接返回 null
    if (head == null) return null;

    // 创建一个字典，用于存储原节点和新节点的映射
    Dictionary<Node, Node> keyValuePairs = new Dictionary<Node, Node>();

    Node curr = head;
    // 第一次遍历，创建新节点并填充字典
    while (curr != null)
    {
        keyValuePairs[curr] = new Node(curr.val); // 将原节点的值赋给新节点
        curr = curr.next; // 移动到下一个原节点
    }

    curr = head; // 重置 curr，准备进行第二次遍历
    // 第二次遍历，设置新节点的 next 和 random 指针
    while (curr != null)
    {
        // 设置新节点的 next 指针
        keyValuePairs[curr].next = curr.next == null ? null : keyValuePairs[curr.next];
        // 设置新节点的 random 指针
        keyValuePairs[curr].random = curr.random == null ? null : keyValuePairs[curr.random];
        curr = curr.next; // 移动到下一个原节点
    }

    // 返回新链表的头节点
    return keyValuePairs[head];
}

三. 步骤解析

1. 初始化

首先，创建一个字典，用于映射原链表中的节点到新链表中的节点。

2. 第一次遍历

遍历原链表，创建新节点并将它们存储在字典中，以原节点为键，新节点为值。

3. 第二次遍历

再次遍历原链表，使用字典设置每个新节点的 next 和 random 指针。

4. 返回新链表的头节点

最终，从字典中返回新链表的头节点。

四. 结论

这种方法确保我们以 O(n) 的时间复杂度和 O(n) 的空间复杂度创建带随机指针的链表的深度复制。使用字典可以有效地映射原节点到新节点，使过程简单易懂。