138. 随机链表的复制 - 题解与详细分析

Ne0inhk

— 7 min read
138. 随机链表的复制 - 题解与详细分析

题目描述

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

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

示例

示例 1：

text

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

示例 2：

text

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

示例 3：

text

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

解题思路

这道题的关键在于如何处理随机指针。由于随机指针可能指向链表中的任意节点，简单的遍历复制无法处理随机指针的指向问题。

核心思想：三步法

  1. 插入复制节点：在原链表的每个节点后面插入一个复制节点
  2. 设置随机指针：根据原节点的随机指针设置复制节点的随机指针
  3. 分离链表：将原链表和复制链表分离

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)（不包括结果链表）。

代码实现

c

/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ // 创建新节点函数 struct Node* BuyNode(int x) { struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node)); NewNode->val = x; NewNode->next = NULL; NewNode->random = NULL; return NewNode; } struct Node* copyRandomList(struct Node* head) { if (head == NULL) return NULL; struct Node* cur = head; // 第一步：在原链表的每个节点后面拷贝一个节点 while(cur) { struct Node* next = cur->next; struct Node* newnode = BuyNode(cur->val); newnode->next = next; cur->next = newnode; cur = next; } // 第二步：设置random指针 cur = head; while(cur) { if(cur->random == NULL) { cur->next->random = NULL; } else { cur->next->random = cur->random->next; } cur = cur->next->next; } // 第三步：将新链表和旧链表断开，并各自链接 cur = head; struct Node* newhead = NULL; struct Node* newtail = NULL; while(cur) { // 将copy节点标记下来 struct Node* temp = cur->next; // 去掉copy节点，然后恢复原链表 cur->next = temp->next; if(newhead == NULL) { newhead = temp; newtail = temp; } else { newtail->next = temp; newtail = newtail->next; } cur = temp->next; } return newhead; }

代码详解

第一步：插入复制节点

c

while(cur) { struct Node* next = cur->next; struct Node* newnode = BuyNode(cur->val); newnode->next = next; cur->next = newnode; cur = next; }

执行效果：

text

原链表：A → B → C → NULL 插入后：A → A' → B → B' → C → C' → NULL

关键点：

  • 在每个原节点后面插入一个复制节点
  • 复制节点的值与原节点相同
  • 保持链表的连接关系

第二步：设置随机指针

c

while(cur) { if(cur->random == NULL) { cur->next->random = NULL; } else { cur->next->random = cur->random->next; } cur = cur->next->next; }

关键点：

  • 如果原节点的random为NULL，复制节点的random也为NULL
  • 如果原节点的random不为NULL，复制节点的random指向原节点random指向的节点的下一个节点（即对应的复制节点）
  • 因为每个原节点后面都跟着它的复制节点，所以 cur->random->next 就是原节点random指向的节点的复制节点

第三步：分离链表

c

while(cur) { struct Node* temp = cur->next; // 复制节点 cur->next = temp->next; // 恢复原链表 if(newhead == NULL) { newhead = temp; newtail = temp; } else { newtail->next = temp; newtail = newtail->next; } cur = temp->next; // 移动到下一个原节点 }

关键点：

  • 将复制节点从原链表中分离出来
  • 恢复原链表的next指针
  • 构建新的复制链表

执行过程可视化

以示例1为例：

原链表：

text

节点0: 7 -> random: NULL 节点1: 13 -> random: 节点0 节点2: 11 -> random: 节点4 节点3: 10 -> random: 节点2 节点4: 1 -> random: 节点0

第一步后：

text

7 → 7' → 13 → 13' → 11 → 11' → 10 → 10' → 1 → 1' → NULL

第二步后（设置random）：

  • 7'.random = NULL
  • 13'.random = 7'
  • 11'.random = 1'
  • 10'.random = 11'
  • 1'.random = 7'

第三步后（分离）：

  • 原链表恢复：7 → 13 → 11 → 10 → 1 → NULL
  • 复制链表：7' → 13' → 11' → 10' → 1' → NULL

复杂度分析

  • 时间复杂度：O(n)，需要遍历链表三次
  • 空间复杂度：O(1)，不包括结果链表，只使用常数级别的额外空间

其他解法

方法二：哈希表法

c

struct Node* copyRandomList(struct Node* head) { if (head == NULL) return NULL; // 创建哈希表，映射原节点到复制节点 struct Node* hash[1000] = {0}; int index = 0; // 第一次遍历：创建所有节点并建立映射 struct Node* cur = head; while (cur != NULL) { hash[index] = BuyNode(cur->val); cur = cur->next; index++; } // 第二次遍历：设置next和random指针 cur = head; index = 0; while (cur != NULL) { if (cur->next != NULL) { hash[index]->next = hash[index + 1]; } if (cur->random != NULL) { // 找到random指向的节点在链表中的位置 struct Node* temp = head; int random_index = 0; while (temp != cur->random) { temp = temp->next; random_index++; } hash[index]->random = hash[random_index]; } cur = cur->next; index++; } return hash[0]; }

优缺点：

  • 优点：思路简单直观
  • 缺点：需要 O(n) 的额外空间，且寻找random索引需要 O(n) 时间

关键点总结

  1. 插入复制节点：这是处理随机指针的关键，使得每个原节点后面都跟着它的复制节点
  2. 随机指针设置：利用 cur->random->next 找到对应的复制节点
  3. 链表分离：仔细处理指针，确保原链表恢复，复制链表正确连接
  4. 边界情况：处理空链表、单个节点等情况

扩展思考

如果链表有环怎么办？

如果原链表有环，这种方法仍然有效，因为：

  1. 插入复制节点后，环的大小会翻倍
  2. 设置随机指针时，逻辑不变
  3. 分离链表时，仍然可以正确分离

如果要求不修改原链表？

可以使用哈希表法，但空间复杂度会变为 O(n)。

应用场景

这种深拷贝带有随机指针的链表在以下场景中有应用：

  1. 对象序列化：深度复制复杂对象结构
  2. 图算法：复制带有随机边的图结构
  3. 数据库：复制关联数据结构
  4. 游戏开发：复制游戏对象及其关联关系

总结

随机链表的复制是一个经典的链表问题，考察了对指针操作和链表结构的深入理解：

  1. 核心技巧：三步法（插入→设置随机指针→分离）
  2. 关键洞察：通过在原节点后插入复制节点，可以轻松找到对应的随机指针目标
  3. 指针操作：需要仔细处理指针，避免内存泄漏或指针错误
  4. 效率优化：O(n) 时间复杂度和 O(1) 空间复杂度（不包括结果）

掌握这种解法对于处理复杂的链表结构和指针操作非常有帮助。

Read more

工具篇-如何在Github Copilot中使用MCP服务?

工具篇-如何在Github Copilot中使用MCP服务?

Model Context Protocol (MCP) 是由 Anthropic 公司于 2024 年 11 月推出的一种开放协议标准，目的在于标准化 LLM 与外部数据源、工具及服务之间的交互方式。MCP 被广泛类比为“AI 领域的 USB-C 接口”。 一、vscode的安装 下载vscodeVisual Studio Code - Code Editing. Redefined安装完成打开 选择copilot，这个是AI助手，帮助你编程  然后注册登录，可以使用GitHub的账号登录，很多工具都可以通过GitHub帐号登录，所以注册一个GitHub帐号是很有必要的。 二、使用MCP 2.1 准备好MCP 先按这篇文章准备好高德地图的MCP：工具篇-Cherry Studio之MCP使用-ZEEKLOG博客 2.2 在Github Copilot中配置 MCP服务

By Ne0inhk
LLaMA-Factory使用

LLaMA-Factory使用

文章目录 * 一、LLAMA-Factory简介 * 二、安装LLaMA-Factory * 三、准备训练数据 * 四、模型训练 * 1. 模型下载 * 2. 全量微调 * 3.lora微调 * 4.QLora微调 * 五、合并模型权重 * 1.模型合并 * 2.测试 一、LLAMA-Factory简介 LLaMA-Factory是一个简单易用且高效的大模型训练框架，支持上百种大模型的训练，框架特性主要包括： * 模型种类：LLaMA、LLaVA、Mistral、Mixtral-MoE、Qwen、Yi、Gemma、Baichuan、ChatGLM、Phi 等等。 * 训练算法：（增量）预训练、（多模态）指令监督微调、奖励模型训练、PPO 训练、DPO 训练、

By Ne0inhk
文心一言开源版测评：能力、易用性与价值的全面解析

文心一言开源版测评：能力、易用性与价值的全面解析

目录 * 一、实测过程记录 * 1. 环境配置详解 * 2. 安装Python环境 * 3. 安装PaddlePaddle（选择CPU版本） * 4. 安装FastDeploy推理引擎 * 5. 下载模型权重及配置文件 * 6. 环境验证脚本 * 7. 常见问题及解决 * 8. 关于GPU加速说明（重要） * 二、模型能力实测：多维度压力测试与代码实战 * 1. 通用理解能力测评（附测试代码） * 1.1 复杂逻辑推理测试 * 1.2 情感极性分析 * 2. 文本生成能力实测 * 风格化写作（带控制参数） * 商业文案生成对比 * 3. 鲁棒性压力测试 * 4. 多模态能力专项测试 * 4.1 图文关联度测评 * 4.2 视觉问答(VQA)实战

By Ne0inhk
AIGC浪潮下，风靡全球的Mcp到底是什么？一文讲懂，技术小白都知道！！

AIGC浪潮下，风靡全球的Mcp到底是什么？一文讲懂，技术小白都知道！！

个人主页-爱因斯晨 文章专栏-AIGC   长大好多烦恼，好愁！ 目录   前言 初步了解 Mcp到底是个啥？ 发展 理论基础 核心组件 使用逻辑 于传统API不同之处 模型推荐   前言 上年这个时候，刚拿到录取通知书。哥哥教我用ai智能体，其实就是向我炫技。当时我问他，为什么不能直接给我生成图表，直接给我生成多好，省得我再去复制了。他说，其实很简单，只要做个接口协议什么的就行，只是目前国内没人做。当时说的很高深，我也听不懂。没想到年底，这个功能就实现内测了。在某种程度上，我也算是预言了哈哈。 初步了解 Mcp到底是个啥？ Mcp，全称 Model Context Protocol，翻译过来是模型上下文协议。你不用管这高大上的名字，简单说，它就是和大 AI 模型聊天时，一种把相关信息整理好、按规矩传给 AI 的方式。

By Ne0inhk