Linkedin中如何复制随机指针

# LinkedIn中如何复制随机指针 ## 引言 在计算机科学和编程面试中，"复制带随机指针的链表"是一个经典问题。这个问题不仅考察对链表结构的理解，还涉及哈希表、指针操作等核心概念。本文将详细探讨如何在LinkedIn（此处应为LeetCode，假设为笔误）或其他编程平台中解决这个问题，并提供多种解决方案的代码实现和复杂度分析。 --- ## 问题描述 给定一个链表，其中每个节点包含： - `val`：节点的值 - `next`：指向下一个节点的指针 - `random`：随机指向链表中任意节点或 `null` 的指针 要求**深度拷贝**这个链表，返回新链表的头节点。新链表中的节点应为全新创建的对象，且 `next` 和 `random` 指针的指向关系与原链表一致。 ### 示例 ```python class Node: def __init__(self, val, next=None, random=None): self.val = val self.next = next self.random = random # 原始链表 original = Node(1) original.next = Node(2) original.random = original.next original.next.random = original.next # 拷贝后的链表应保持相同的结构 

---

解决方案

方法一：哈希表映射（O(N)时间，O(N)空间）

步骤

1. 第一次遍历：创建原节点到新节点的映射。

    old_to_new = {None: None} # 处理random指向null的情况 current = head while current: old_to_new[current] = Node(current.val) current = current.next 

2. 第二次遍历：根据映射关系设置 next 和 random 指针。

    current = head while current: new_node = old_to_new[current] new_node.next = old_to_new[current.next] new_node.random = old_to_new[current.random] current = current.next 

3. 返回 old_to_new[head]。

复杂度分析

• 时间：O(N)，两次线性遍历。
• 空间：O(N)，哈希表存储所有节点。

---

方法二：原地修改（O(N)时间，O(1)空间）

步骤

1. 第一次遍历：在每个原节点后插入拷贝节点。

    current = head while current: new_node = Node(current.val, current.next) current.next = new_node current = new_node.next 

2. 第二次遍历：设置 random 指针。

    current = head while current: if current.random: current.next.random = current.random.next current = current.next.next 

3. 第三次遍历：分离原链表和拷贝链表。

    dummy = Node(0) copy_current = dummy current = head while current: copy_current.next = current.next current.next = current.next.next copy_current = copy_current.next current = current.next 

4. 返回 dummy.next。

复杂度分析

• 时间：O(N)，三次线性遍历。
• 空间：O(1)，仅使用常量额外空间。

---

代码实现

Python示例（哈希表法）

def copyRandomList(head): if not head: return None old_to_new = {} # 第一次遍历：创建节点映射 current = head while current: old_to_new[current] = Node(current.val) current = current.next # 第二次遍历：设置指针 current = head while current: old_to_new[current].next = old_to_new.get(current.next) old_to_new[current].random = old_to_new.get(current.random) current = current.next return old_to_new[head] 

Java示例（原地修改法）

public Node copyRandomList(Node head) { if (head == null) return null; // 插入拷贝节点 Node current = head; while (current != null) { Node temp = new Node(current.val); temp.next = current.next; current.next = temp; current = temp.next; } // 设置random指针 current = head; while (current != null) { if (current.random != null) { current.next.random = current.random.next; } current = current.next.next; } // 分离链表 Node dummy = new Node(0); Node copyCurrent = dummy; current = head; while (current != null) { copyCurrent.next = current.next; current.next = current.next.next; copyCurrent = copyCurrent.next; current = current.next; } return dummy.next; } 

---

常见问题

1. 为什么需要深度拷贝？

• 浅拷贝仅复制引用，新链表的节点仍指向原链表的节点，修改会影响原链表。

2. 如何处理环状链表？

• 两种方法均能正确处理环状结构，因为哈希表或原地插入会完整保留拓扑关系。

3. 哪种方法更优？

• 哈希表法更直观，适合面试快速实现；原地修改法空间更优，但代码复杂度较高。

---

总结

复制带随机指针的链表问题需要巧妙处理指针关系。掌握哈希表和原地修改两种方法，能帮助你在LinkedIn（LeetCode）等平台的算法面试中游刃有余。建议根据实际场景选择空间或时间优先的策略。 “`

注：假设标题中的”Linkedin”为”LeetCode”笔误，若需调整内容方向请说明。