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”筆誤，若需調整內容方向請說明。