复杂链表的复制（链表的复制构造函数）

# 简介在计算机科学中，链表是一种常见的数据结构，用于存储一系列节点，每个节点包含数据和指向下一个节点的指针。而复杂链表则是在普通链表的基础上增加了额外的复杂性，比如每个节点可能还包含一个指向链表中其他节点的“随机指针”。这种数据结构的复制是一个经典问题，在面试和实际开发中都有重要的应用价值。本文将详细介绍复杂链表的复制过程，从基础概念到具体实现步骤，并通过代码示例帮助读者深入理解这一过程。---## 多级标题1. 什么是复杂链表 2. 为什么需要复制复杂链表 3. 常见的复制方法 4. 实现步骤详解 5. 示例代码解析 ---## 1. 什么是复杂链表复杂链表与普通链表的主要区别在于每个节点除了包含普通的“下一个节点”指针外，还可能包含一个“随机指针”。这个随机指针可以指向链表中的任意节点或为空。例如，一个复杂链表的结构如下：```plaintext Node 1 -> Node 2 -> Node 3 | | | Random -> Node 3 Random -> Node 1 ```在这个例子中： - 每个节点有一个“下一个节点”的指针。 - 每个节点还有一个“随机指针”，它指向链表中的某个节点。---## 2. 为什么需要复制复杂链表在实际开发中，我们需要对复杂链表进行复制的原因有很多。例如： - 数据备份：当需要保存当前链表的状态时，可以创建一份副本。 - 并发操作：在多线程环境中，为了避免数据冲突，可能会对链表进行复制。 - 算法设计：某些算法需要在不改变原链表的情况下操作副本。因此，掌握复杂链表的复制方法是解决许多问题的基础。---## 3. 常见的复制方法复杂链表的复制主要有两种常见方法： 1.

两遍遍历法

：分为两步完成，先复制普通节点，再处理随机指针。 2.

哈希表辅助法

：使用哈希表记录原节点和新节点之间的映射关系。这两种方法各有优缺点，我们将分别介绍它们的实现细节。---## 4. 实现步骤详解### 方法一：两遍遍历法#### 步骤1：复制普通节点 首先，我们遍历原始链表，依次复制每个节点并插入到原节点之后。例如，如果原始链表为 `A -> B -> C`，那么复制后的链表会变成 `A -> A' -> B -> B' -> C -> C'`。#### 步骤2：处理随机指针 接下来，再次遍历链表，为新节点设置随机指针。由于新节点紧随其原始节点之后，所以可以通过公式 `newNode.random = originalNode.random.next` 来设置新节点的随机指针。#### 步骤3：分离链表 最后，将链表拆分成两个独立的部分：一个是原始链表，另一个是复制后的链表。### 方法二：哈希表辅助法#### 步骤1：构建映射关系 使用一个哈希表（如字典）来记录原节点和新节点的对应关系。遍历原始链表时，将每个原节点作为键，对应的复制节点作为值存入哈希表。#### 步骤2：复制节点和随机指针 根据哈希表的关系，逐一复制节点并设置随机指针。由于哈希表已经记录了所有节点的映射，这一步非常简单。#### 步骤3：返回复制链表的头节点 完成所有节点的复制后，返回复制链表的头节点即可。---## 5. 示例代码解析以下是基于两遍遍历法的 Python 实现代码：```python class Node:def __init__(self, val=0):self.val = valself.next = Noneself.random = Nonedef copyRandomList(head):if not head:return None# 第一遍遍历：复制节点并插入到原节点之后current = headwhile current:new_node = Node(current.val)new_node.next = current.nextcurrent.next = new_nodecurrent = new_node.next# 第二遍遍历：设置随机指针current = headwhile current:if current.random:current.next.random = current.random.nextcurrent = current.next.next# 第三遍遍历：分离链表original = headcopied = head.nextcopied_head = copiedwhile original:original.next = original.next.nextif copied.next:copied.next = copied.next.nextoriginal = original.nextcopied = copied.nextreturn copied_head# 测试代码 if __name__ == "__main__":node1 = Node(1)node2 = Node(2)node3 = Node(3)node1.next = node2node2.next = node3node1.random = node3node2.random = node1node3.random = node2copied_head = copyRandomList(node1)print("Copied List:")while copied_head:print(f"Value: {copied_head.val}, Random: {copied_head.random.val if copied_head.random else 'None'}")copied_head = copied_head.next ```---## 总结复杂链表的复制虽然看起来复杂，但通过分步骤的方法可以轻松实现。无论是两遍遍历法还是哈希表辅助法，都能有效解决问题。掌握这些方法不仅有助于解决具体问题，还能提升算法设计的能力。希望本文能帮助你更好地理解和应用复杂链表的复制技术！

简介在计算机科学中，链表是一种常见的数据结构，用于存储一系列节点，每个节点包含数据和指向下一个节点的指针。而复杂链表则是在普通链表的基础上增加了额外的复杂性，比如每个节点可能还包含一个指向链表中其他节点的“随机指针”。这种数据结构的复制是一个经典问题，在面试和实际开发中都有重要的应用价值。本文将详细介绍复杂链表的复制过程，从基础概念到具体实现步骤，并通过代码示例帮助读者深入理解这一过程。---

多级标题1. 什么是复杂链表 2. 为什么需要复制复杂链表 3. 常见的复制方法 4. 实现步骤详解 5. 示例代码解析 ---

1. 什么是复杂链表复杂链表与普通链表的主要区别在于每个节点除了包含普通的“下一个节点”指针外，还可能包含一个“随机指针”。这个随机指针可以指向链表中的任意节点或为空。例如，一个复杂链表的结构如下：```plaintext Node 1 -> Node 2 -> Node 3 | | | Random -> Node 3 Random -> Node 1 ```在这个例子中： - 每个节点有一个“下一个节点”的指针。 - 每个节点还有一个“随机指针”，它指向链表中的某个节点。---

2. 为什么需要复制复杂链表在实际开发中，我们需要对复杂链表进行复制的原因有很多。例如： - 数据备份：当需要保存当前链表的状态时，可以创建一份副本。 - 并发操作：在多线程环境中，为了避免数据冲突，可能会对链表进行复制。 - 算法设计：某些算法需要在不改变原链表的情况下操作副本。因此，掌握复杂链表的复制方法是解决许多问题的基础。---

3. 常见的复制方法复杂链表的复制主要有两种常见方法： 1. **两遍遍历法**：分为两步完成，先复制普通节点，再处理随机指针。 2. **哈希表辅助法**：使用哈希表记录原节点和新节点之间的映射关系。这两种方法各有优缺点，我们将分别介绍它们的实现细节。---

4. 实现步骤详解

方法一：两遍遍历法

步骤1：复制普通节点 首先，我们遍历原始链表，依次复制每个节点并插入到原节点之后。例如，如果原始链表为 `A -> B -> C`，那么复制后的链表会变成 `A -> A' -> B -> B' -> C -> C'`。

步骤2：处理随机指针 接下来，再次遍历链表，为新节点设置随机指针。由于新节点紧随其原始节点之后，所以可以通过公式 `newNode.random = originalNode.random.next` 来设置新节点的随机指针。

步骤3：分离链表 最后，将链表拆分成两个独立的部分：一个是原始链表，另一个是复制后的链表。

方法二：哈希表辅助法

步骤1：构建映射关系 使用一个哈希表（如字典）来记录原节点和新节点的对应关系。遍历原始链表时，将每个原节点作为键，对应的复制节点作为值存入哈希表。

步骤2：复制节点和随机指针 根据哈希表的关系，逐一复制节点并设置随机指针。由于哈希表已经记录了所有节点的映射，这一步非常简单。

步骤3：返回复制链表的头节点 完成所有节点的复制后，返回复制链表的头节点即可。---

5. 示例代码解析以下是基于两遍遍历法的 Python 实现代码：```python class Node:def __init__(self, val=0):self.val = valself.next = Noneself.random = Nonedef copyRandomList(head):if not head:return None

第一遍遍历：复制节点并插入到原节点之后current = headwhile current:new_node = Node(current.val)new_node.next = current.nextcurrent.next = new_nodecurrent = new_node.next

第二遍遍历：设置随机指针current = headwhile current:if current.random:current.next.random = current.random.nextcurrent = current.next.next

第三遍遍历：分离链表original = headcopied = head.nextcopied_head = copiedwhile original:original.next = original.next.nextif copied.next:copied.next = copied.next.nextoriginal = original.nextcopied = copied.nextreturn copied_head

测试代码 if __name__ == "__main__":node1 = Node(1)node2 = Node(2)node3 = Node(3)node1.next = node2node2.next = node3node1.random = node3node2.random = node1node3.random = node2copied_head = copyRandomList(node1)print("Copied List:")while copied_head:print(f"Value: {copied_head.val}, Random: {copied_head.random.val if copied_head.random else 'None'}")copied_head = copied_head.next ```---

总结复杂链表的复制虽然看起来复杂，但通过分步骤的方法可以轻松实现。无论是两遍遍历法还是哈希表辅助法，都能有效解决问题。掌握这些方法不仅有助于解决具体问题，还能提升算法设计的能力。希望本文能帮助你更好地理解和应用复杂链表的复制技术！