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”笔误，若需调整内容方向请说明。