当前位置： 首页 > news >正文

用100道题拿下你的算法面试（链表篇-7）：复制带随机指针的链表

news 2026/5/13 2:17:52

一、面试问题

给定一个链表的头节点，链表中每个节点都包含两个指针：一个指向下一个节点的next指针，以及一个指向链表中任意节点的random指针。请复制该链表，并返回新链表的头节点。

二、【朴素解法】使用哈希表 —— 时间复杂度 O (n)，空间复杂度 O (n)

(一) 解法思路

  1. 核心思路是：为原链表中的每个节点创建一个对应的新节点，并将这些节点存储在哈希表中，然后更新新节点的next指针和random指针。
  2. 创建一个哈希表mp，用于映射原节点到新节点。遍历原链表，对每个节点curr，创建一个对应的新节点，并存储到哈希表中：mp[curr] = new Node()。
  3. 再次遍历链表，更新新节点的next和random指针：
  • mp[curr]->next = mp[curr->next]
  • mp[curr]->random = mp[curr->random]
  1. 返回mp[head]作为复制后链表的头节点。

(二) 使用 5 种语言实现

1. C++

#include <iostream> #include <unordered_map> using namespace std; class Node { public: int data; Node* next; Node* random; Node(int x) { data = x; next = random = NULL; } }; Node* cloneLinkedList(Node* head) { unordered_map<Node*, Node*> mp; Node *curr = head; // 遍历原链表，存储与原节点对应的新节点 while (curr != NULL) { mp[curr] = new Node(curr->data); curr = curr->next; } curr = head; // 循环更新新节点的 next 和 random 指针 while (curr != NULL) { mp[curr]->next = mp[curr->next]; mp[curr]->random = mp[curr->random]; curr = curr->next; } return mp[head]; } void printList(Node* head) { while (head != NULL) { cout << head->data << "("; if(head->random) cout << head->random->data << ")"; else cout << "null" << ")"; if(head->next != NULL) cout << " -> "; head = head->next; } cout << endl; } int main() { // 创建带随机指针的链表 Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->next->next = new Node(4); head->next->next->next->next = new Node(5); head->random = head->next->next; head->next->random = head; head->next->next->random = head->next->next->next->next; head->next->next->next->random = head->next->next; head->next->next->next->next->random = head->next; // 打印原始链表 cout << "Original linked list:\n"; printList(head); Node* clonedList = cloneLinkedList(head); // 打印复制后的链表 cout << "Cloned linked list:\n"; printList(clonedList); return 0; }

2. Java

import java.util.HashMap; import java.util.Map; class Node { int data; Node next; Node random; Node(int x) { data = x; next = null; random = null; } } class DSA { static Node cloneLinkedList(Node head) { Map<Node, Node> mp = new HashMap<>(); Node curr = head; // 遍历原链表，存储与原节点对应的新节点 while (curr != null) { mp.put(curr, new Node(curr.data)); curr = curr.next; } curr = head; // 循环更新新节点的 next 和 random 指针 while (curr != null) { Node newNode = mp.get(curr); newNode.next = mp.get(curr.next); newNode.random = mp.get(curr.random); curr = curr.next; } return mp.get(head); } static void printList(Node head) { while (head != null) { System.out.print(head.data + "("); if (head.random != null) System.out.print(head.random.data + ")"); else System.out.print("null" + ")"); if (head.next != null) System.out.print(" -> "); head = head.next; } System.out.println(); } public static void main(String[] args) { // 创建带随机指针的链表 Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.random = head.next.next; head.next.random = head; head.next.next.random = head.next.next.next.next; head.next.next.next.random = head.next.next; head.next.next.next.next.random = head.next; // 打印原始链表 System.out.println("Original linked list:"); printList(head); Node clonedList = cloneLinkedList(head); // 打印复制后的链表 System.out.println("Cloned linked list:"); printList(clonedList); } }

3. Python

class Node: def __init__(self, x): self.data = x self.next = None self.random = None def cloneLinkedList(head): nodeMap = {} curr = head # 遍历原链表，存储与原节点对应的新节点 while curr is not None: nodeMap[curr] = Node(curr.data) curr = curr.next curr = head # 循环更新新节点的 next 和 random 指针 while curr is not None: newNode = nodeMap[curr] newNode.next = nodeMap.get(curr.next) newNode.random = nodeMap.get(curr.random) curr = curr.next return nodeMap.get(head) def printList(head): curr = head while curr is not None: print(f'{curr.data}(', end='') if curr.random: print(f'{curr.random.data})', end='') else: print('null)', end='') if curr.next is not None: print(' -> ', end='') curr = curr.next print() if __name__ == "__main__": # 创建带随机指针的链表 head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.random = head.next.next head.next.random = head head.next.next.random = head.next.next.next.next head.next.next.next.random = head.next.next head.next.next.next.next.random = head.next # 打印原始链表 print("Original linked list:") printList(head) clonedList = cloneLinkedList(head) # 打印复制后的链表 print("Cloned linked list:") printList(clonedList)

4. C#

using System; using System.Collections.Generic; class Node { public int Data; public Node Next; public Node Random; public Node(int x) { Data = x; Next = null; Random = null; } } class DSA { static Node cloneLinkedList(Node head) { Dictionary<Node, Node> mp = new Dictionary<Node, Node>(); Node curr = head; // 遍历原链表，存储与原节点对应的新节点 while (curr != null) { mp[curr] = new Node(curr.Data); curr = curr.Next; } curr = head; // 循环更新新节点的 next 和 random 指针 while (curr != null) { Node newNode = mp[curr]; if(curr.Next != null) newNode.Next = mp[curr.Next]; newNode.Random = mp[curr.Random]; curr = curr.Next; } return mp[head]; } static void PrintList(Node head) { while (head != null) { Console.Write(head.Data + "("); if (head.Random != null) Console.Write(head.Random.Data); else Console.Write("null"); Console.Write(")"); if (head.Next != null) Console.Write(" -> "); head = head.Next; } Console.WriteLine(); } static void Main(string[] args) { // 创建带随机指针的链表 Node head = new Node(1); head.Next = new Node(2); head.Next.Next = new Node(3); head.Next.Next.Next = new Node(4); head.Next.Next.Next.Next = new Node(5); head.Random = head.Next.Next; head.Next.Random = head; head.Next.Next.Random = head.Next.Next.Next.Next; head.Next.Next.Next.Random = head.Next.Next; head.Next.Next.Next.Next.Random = head.Next; // 打印原始链表 Console.WriteLine("Original linked list:"); PrintList(head); Node clonedList = cloneLinkedList(head); // 打印复制后的链表 Console.WriteLine("Cloned linked list:"); PrintList(clonedList); } }

5. JavaScript

class Node { constructor(data) { this.data = data; this.next = null; this.random = null; } } function cloneLinkedList(head) { const mp = new Map(); let curr = head; // 遍历原链表，存储与原节点对应的新节点 while (curr !== null) { mp.set(curr, new Node(curr.data)); curr = curr.next; } curr = head; // 循环更新新节点的 next 和 random 指针 while (curr !== null) { const newNode = mp.get(curr); newNode.next = mp.get(curr.next) || null; newNode.random = mp.get(curr.random) || null; curr = curr.next; } return mp.get(head) || null; } function printList(head) { let result = ""; while (head !== null) { result += head.data + "("; result += head.random ? head.random.data : "null"; result += ")"; if (head.next !== null) { result += " -> "; } head = head.next; } console.log(result); } // 驱动代码 // 创建带随机指针的链表 const head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.random = head.next.next; head.next.random = head; head.next.next.random = head.next.next.next.next; head.next.next.next.random = head.next.next; head.next.next.next.next.random = head.next; // 打印原始链表 console.log("Original linked list:"); printList(head); const clonedList = cloneLinkedList(head); // 打印复制后的链表 console.log("Cloned linked list:"); printList(clonedList);

(三)代码输出和算法复杂度

输出：

Original linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Cloned linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2)

时间复杂度：O(n)。

空间复杂度：O(n)。

三、【最优方法】原地插入节点 —— 时间复杂度 O (n)，空间复杂度 O (1)

(一) 解法思路

核心思路：创建原节点的副本，不使用哈希表存储，而是将副本节点直接插入到原节点与下一个节点之间，这样新节点会出现在交替位置上。

  1. 遍历链表，在每个原节点后面插入一个克隆节点。对每个节点 X，创建 X'，并放置为X → X' → next。
  2. 再次遍历链表，更新克隆节点的 random 指针。规则：X'.random = X.random.next（如果 random 指针存在）。
  3. 第三次遍历链表，将两个链表拆分：恢复原链表的链接，并提取出克隆链表。
  4. 修正指针：
    • 原节点.next = 原节点.next.next
    • 克隆节点.next = 克隆节点.next.next
  1. 返回克隆链表的头节点。

(二) 使用 5 种语言实现

1. C++

#include <iostream> using namespace std; class Node { public: int data; Node *next, *random; Node(int x) { data = x; next = random = NULL; } }; Node* cloneLinkedList(Node* head) { if (head == NULL) { return NULL; } // 创建新节点，并将其插入到原节点的下一个位置 Node* curr = head; while (curr != NULL) { Node* newNode = new Node(curr->data); newNode->next = curr->next; curr->next = newNode; curr = newNode->next; } // 设置新节点的随机指针 curr = head; while (curr != NULL) { if (curr->random != NULL) curr->next->random = curr->random->next; curr = curr->next->next; } // 将新节点与原节点分离 curr = head; Node* clonedHead = head->next; Node* clone = clonedHead; while (clone->next != NULL) { // 更新原节点和克隆节点的下一个节点 curr->next = curr->next->next; clone->next = clone->next->next; // 将原链表和克隆链表的指针移动到各自的下一个节点 curr = curr->next; clone = clone->next; } curr->next = NULL; clone->next = NULL; return clonedHead; } void printList(Node* head) { while (head != NULL) { cout << head->data << "("; if(head->random) cout << head->random->data << ")"; else cout << "null" << ")"; if(head->next != NULL) cout << " -> "; head = head->next; } cout << endl; } int main() { // 创建带随机指针的链表 Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->next->next = new Node(4); head->next->next->next->next = new Node(5); head->random = head->next->next; head->next->random = head; head->next->next->random = head->next->next->next->next; head->next->next->next->random = head->next->next; head->next->next->next->next->random = head->next; // 打印原始链表 cout << "Original linked list:\n"; printList(head); Node* clonedList = cloneLinkedList(head); // 打印克隆后的链表 cout << "Cloned linked list:\n"; printList(clonedList); return 0; }

2. Java

class Node { int data; Node next, random; Node(int x) { data = x; next = random = null; } } class DSA { static Node cloneLinkedList(Node head) { if (head == null) { return null; } // 创建新节点，并将其插入到原节点的下一个位置 Node curr = head; while (curr != null) { Node newNode = new Node(curr.data); newNode.next = curr.next; curr.next = newNode; curr = newNode.next; } // 设置新节点的随机指针 curr = head; while (curr != null) { if (curr.random != null) { curr.next.random = curr.random.next; } curr = curr.next.next; } // 将新节点与原节点分离 curr = head; Node clonedHead = head.next; Node clone = clonedHead; while (clone.next != null) { // 更新原节点和克隆节点的下一个节点 curr.next = curr.next.next; clone.next = clone.next.next; // 将原链表和克隆链表的指针移动到各自的下一个节点 curr = curr.next; clone = clone.next; } curr.next = null; clone.next = null; return clonedHead; } static void printList(Node head) { while (head != null) { System.out.print(head.data + "("); if (head.random != null) { System.out.print(head.random.data); } else { System.out.print("null"); } System.out.print(")"); if (head.next != null) { System.out.print(" -> "); } head = head.next; } System.out.println(); } public static void main(String[] args) { // 创建带随机指针的链表 Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.random = head.next.next; head.next.random = head; head.next.next.random = head.next.next.next.next; head.next.next.next.random = head.next.next; head.next.next.next.next.random = head.next; // 打印原始链表 System.out.println("Original linked list:"); printList(head); Node clonedList = cloneLinkedList(head); // 打印克隆后的链表 System.out.println("Cloned linked list:"); printList(clonedList); } }

3. Python

class Node: def __init__(self, x): self.data = x self.next = None self.random = None def cloneLinkedList(head): if head is None: return None # 创建新节点，并将其插入到原节点的下一个位置 curr = head while curr is not None: newNode = Node(curr.data) newNode.next = curr.next curr.next = newNode curr = newNode.next # 设置新节点的随机指针 curr = head while curr is not None: if curr.random is not None: curr.next.random = curr.random.next curr = curr.next.next # 将新节点与原节点分离 curr = head clonedHead = head.next clone = clonedHead while clone.next is not None: # 更新原节点和克隆节点的下一个节点 curr.next = curr.next.next clone.next = clone.next.next # 将原链表和克隆链表的指针移动到各自的下一个节点 curr = curr.next clone = clone.next curr.next = None clone.next = None return clonedHead def printList(head): while head is not None: print(f"{head.data}(", end="") if head.random: print(f"{head.random.data})", end="") else: print("null)", end="") if head.next is not None: print(" -> ", end="") head = head.next print() if __name__ == "__main__": # 创建带随机指针的链表 head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.random = head.next.next head.next.random = head head.next.next.random = head.next.next.next.next head.next.next.next.random = head.next.next head.next.next.next.next.random = head.next # 打印原始链表 print("Original linked list:") printList(head) clonedList = cloneLinkedList(head) # 打印克隆后的链表 print("Cloned linked list:") printList(clonedList)

4. C#

using System; using System.Collections.Generic; class Node { public int Data; public Node Next, Random; public Node(int x) { Data = x; Next = Random = null; } } class DSA { static Node cloneLinkedList(Node head) { if (head == null) return null; // 创建新节点，并将其插入到原节点的下一个位置 Node curr = head; while (curr != null) { Node newNode = new Node(curr.Data); newNode.Next = curr.Next; curr.Next = newNode; curr = newNode.Next; } // 设置新节点的随机指针 curr = head; while (curr != null) { if (curr.Random != null) curr.Next.Random = curr.Random.Next; curr = curr.Next.Next; } // 将新节点与原节点分离 curr = head; Node clonedHead = head.Next; Node clone = clonedHead; while (clone.Next != null) { // 更新原节点和克隆节点的下一个节点 curr.Next = curr.Next.Next; clone.Next = clone.Next.Next; // 将原链表和克隆链表的指针移动到各自的下一个节点 curr = curr.Next; clone = clone.Next; } curr.Next = null; clone.Next = null; return clonedHead; } static void printList(Node head) { while (head != null) { Console.Write(head.Data + "("); if (head.Random != null) Console.Write(head.Random.Data + ")"); else Console.Write("null)"); if (head.Next != null) Console.Write(" -> "); head = head.Next; } Console.WriteLine(); } public static void Main() { // 创建带随机指针的链表 Node head = new Node(1); head.Next = new Node(2); head.Next.Next = new Node(3); head.Next.Next.Next = new Node(4); head.Next.Next.Next.Next = new Node(5); head.Random = head.Next.Next; head.Next.Random = head; head.Next.Next.Random = head.Next.Next.Next.Next; head.Next.Next.Next.Random = head.Next.Next; head.Next.Next.Next.Next.Random = head.Next; // 打印原始链表 Console.WriteLine("Original linked list:"); printList(head); Node clonedList = cloneLinkedList(head); // 打印克隆后的链表 Console.WriteLine("Cloned linked list:"); printList(clonedList); } }

5. JavaScript

class Node { constructor(data) { this.data = data; this.next = null; this.random = null; } } function cloneLinkedList(head) { if (head === null) { return null; } // 创建新节点，并将其插入到原节点的下一个位置 let curr = head; while (curr !== null) { let newNode = new Node(curr.data); newNode.next = curr.next; curr.next = newNode; curr = newNode.next; } // 设置新节点的随机指针 curr = head; while (curr !== null) { if (curr.random !== null) { curr.next.random = curr.random.next; } curr = curr.next.next; } // 将新节点与原节点分离 curr = head; let clonedHead = head.next; let clone = clonedHead; while (clone.next !== null) { // 更新原节点和克隆节点的下一个节点 curr.next = curr.next.next; clone.next = clone.next.next; // 将原链表和克隆链表的指针移动到各自的下一个节点 curr = curr.next; clone = clone.next; } curr.next = null; clone.next = null; return clonedHead; } function printList(head) { let result = ""; while (head !== null) { result += head.data + "("; result += head.random ? head.random.data : "null"; result += ")"; if (head.next !== null) { result += " -> "; } head = head.next; } console.log(result); } // 创建带随机指针的链表 let head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.random = head.next.next; head.next.random = head; head.next.next.random = head.next.next.next.next; head.next.next.next.random = head.next.next; head.next.next.next.next.random = head.next; // 打印原始链表 console.log("Original linked list:"); printList(head); let clonedList = cloneLinkedList(head); // 打印克隆后的链表 console.log("Cloned linked list:"); printList(clonedList);

(三)代码输出和算法复杂度

输出：

Original linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Cloned linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2)

时间复杂度：O(n)。

空间复杂度：O(1)。

http://www.jsqmd.com/news/805934/

相关文章：

  • NotebookLM未公开的Obsidian插件桥接协议（内部文档泄露版），仅限前500名技术决策者获取
  • 5分钟快速上手D3KeyHelper：暗黑3鼠标宏工具终极配置教程
  • Elasticsearch与Gemini大模型集成：自然语言查询与智能数据洞察实践
  • 2026中小企业OA软件排行榜TOP10（精简版）
  • 最小扩张三角剖分：算法优化与计算几何实践
  • 终极UE4SS游戏Mod开发指南：从零开始掌握虚幻引擎脚本系统
  • Go语言构建高效命令行工具集：从设计到工程化实践
  • Cursor AI 使用限制突破：设备标识重置与多账户管理的技术实现
  • 数字记忆保险箱：用WeChatExporter永久保存微信聊天记录
  • 前端代码部署到centos7 服务器上
  • 半导体并购潮与IP商业模式演进：从单点IP到系统级平台化方案
  • LangChain集成MCP协议：构建模块化AI应用的新范式
  • React实战：从零构建Airbnb风格前端应用的技术架构与实现
  • windows构建mamba环境
  • 从零解析BraTs：Python实战.nii多模态MRI数据加载与可视化
  • JPlag代码抄袭检测：你的学术诚信守护神
  • WAS Node Suite高性能图像批处理架构设计与状态管理优化策略深度解析
  • 2026杭州商用空调清洗专业指南：杭州工厂保洁/杭州店铺保洁/杭州消毒杀菌/杭州高空外墙清洗/杭州上门保洁/杭州中央空调消毒/选择指南 - 优质品牌商家
  • 算法对比别再只看Friedman检验了：聊聊Nemenyi和Bonferroni-Dunn的‘悖论’与实战避坑
  • Midjourney 2026将取消/imagine？不，它正悄悄部署「自然语言-图像-3D资产」三合一原生工作流（附实测对比数据）
  • 云原生监控一体化实践：从零部署mco实现指标、日志、追踪统一管理
  • WeChatExporter：微信聊天记录永久备份的终极解决方案
  • 2026年Q2商用游戏机选型指南：电玩城游戏机、出票游戏机、实物五门文审机、扣篮王游戏机、文审游戏机、扣篮王、商用游戏机选择指南 - 优质品牌商家
  • 单片机语法2
  • 数字示波器在EMI预测试中的关键技术应用
  • Tempera风格提示词结构全解析，深度解读色阶压缩率、笔触衰减系数与基底纹理权重配置
  • 2026年5月新消息：陕西打包箱房服务商如何选择？河北圣硕金属制品有限公司实力解析 - 2026年企业推荐榜
  • 从零构建Fresco工作流：设计师私藏的3阶段精修链（线稿强化→湿扩散控制→干刷边缘增强）
  • 从开题到见刊仅112天：一位青椒用Perplexity Pro重构写作范式的完整时间日志（含失败复盘数据）
  • 3步快速上手：Windows安卓应用安装器完全指南