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

一、面试问题给定一个链表的头节点链表中每个节点都包含两个指针一个指向下一个节点的next指针以及一个指向链表中任意节点的random指针。请复制该链表并返回新链表的头节点。二、【朴素解法】使用哈希表 —— 时间复杂度 O (n)空间复杂度 O (n)(一) 解法思路核心思路是为原链表中的每个节点创建一个对应的新节点并将这些节点存储在哈希表中然后更新新节点的next指针和random指针。创建一个哈希表mp用于映射原节点到新节点。遍历原链表对每个节点curr创建一个对应的新节点并存储到哈希表中mp[curr] new Node()。再次遍历链表更新新节点的next和random指针mp[curr]-next mp[curr-next]mp[curr]-random mp[curr-random]返回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_mapNode*, 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. Javaimport 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) { MapNode, 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. Pythonclass 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) { DictionaryNode, Node mp new DictionaryNode, 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. JavaScriptclass 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)(一) 解法思路核心思路创建原节点的副本不使用哈希表存储而是将副本节点直接插入到原节点与下一个节点之间这样新节点会出现在交替位置上。遍历链表在每个原节点后面插入一个克隆节点。对每个节点 X创建 X并放置为X → X → next。再次遍历链表更新克隆节点的 random 指针。规则X.random X.random.next如果 random 指针存在。第三次遍历链表将两个链表拆分恢复原链表的链接并提取出克隆链表。修正指针原节点.next 原节点.next.next克隆节点.next 克隆节点.next.next返回克隆链表的头节点。(二) 使用 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. Javaclass 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. Pythonclass 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. JavaScriptclass 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)。