leetcode如何實現復制帶隨機指針的鏈表

# LeetCode如何實現復制帶隨機指針的鏈表

## 問題描述

LeetCode第138題"復制帶隨機指針的鏈表"(Copy List with Random Pointer)要求我們深度復制一個特殊的鏈表結構。這種鏈表的每個節點除了包含標準的`val`和`next`指針外，還包含一個可能指向鏈表中任意節點或為`null`的`random`指針。

```python
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

問題分析

普通鏈表的復制非常簡單，只需遍歷原鏈表逐個創建新節點即可。但帶隨機指針的鏈表存在以下難點：

1. 隨機指針的指向關系：新鏈表中節點的random指針必須正確指向新鏈表中的對應節點，而非原鏈表節點
2. 可能存在的循環引用：random指針可能形成環，需要避免無限循環
3. 時間復雜度與空間復雜度：如何在合理復雜度內完成復制

解決方案

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

算法步驟

1. 第一次遍歷：創建所有新節點，并用哈希表建立原節點到新節點的映射
2. 第二次遍歷：通過哈希表完善新節點的next和random指針關系

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None
    
    # 建立原節點到新節點的映射
    mapping = {}
    curr = head
    while curr:
        mapping[curr] = Node(curr.val)
        curr = curr.next
    
    # 設置新節點的next和random指針
    curr = head
    while curr:
        if curr.next:
            mapping[curr].next = mapping[curr.next]
        if curr.random:
            mapping[curr].random = mapping[curr.random]
        curr = curr.next
    
    return mapping[head]

復雜度分析

• 時間復雜度：O(N)，兩次線性遍歷
• 空間復雜度：O(N)，哈希表存儲所有節點映射

方法二：節點穿插法（O(N)時間，O(1)空間）

算法步驟

1. 第一次遍歷：在每個原節點后插入對應的新節點

   
   原鏈表：A -> B -> C
   穿插后：A -> A' -> B -> B' -> C -> C'
   

2. 第二次遍歷：設置新節點的random指針
3. 第三次遍歷：分離新舊鏈表

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None
    
    # 1. 在每個原節點后插入新節點
    curr = head
    while curr:
        new_node = Node(curr.val)
        new_node.next = curr.next
        curr.next = new_node
        curr = new_node.next
    
    # 2. 設置新節點的random指針
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    
    # 3. 分離兩個鏈表
    curr = head
    new_head = head.next
    while curr:
        temp = curr.next
        curr.next = temp.next
        if temp.next:
            temp.next = temp.next.next
        curr = curr.next
    
    return new_head

復雜度分析

• 時間復雜度：O(N)，三次線性遍歷
• 空間復雜度：O(1)，僅使用常數額外空間（不考慮輸出占用的空間）

邊界情況處理

在實際編碼中需要考慮以下邊界情況：

1. 空鏈表輸入：直接返回None
2. 單個節點：確保random指針正確處理
3. random指向自身：如A.random = A
4. 多個random指向同一節點：確保不會重復創建節點

測試用例示例

# 示例1
# 輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
# 輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

# 示例2
# 輸入：head = [[1,1],[2,1]]
# 輸出：[[1,1],[2,1]]

# 示例3
# 輸入：head = [[3,null],[3,0],[3,null]]
# 輸出：[[3,null],[3,0],[3,null]]

方法比較

常見面試問題

1. 如何處理循環引用的random指針？

   • 兩種方法都能正確處理，因為哈希表記錄了已創建的節點，穿插法通過原節點直接找到對應新節點

2. 為什么穿插法不需要額外空間？

   • 它利用了原鏈表的next指針臨時存儲新節點，實際上空間開銷存在于新鏈表本身

3. 如果鏈表很大，哪種方法更優？

   • 在空間受限環境下，穿插法更優；否則哈希表法代碼更簡潔

擴展思考

1. 圖的深拷貝：這道題本質上是圖的深拷貝問題，每個節點是圖頂點，next和random指針是邊
2. 多線程環境：如果鏈表可能被并發修改，需要加鎖或使用不可變結構
3. 持久化數據結構：如何設計數據結構使得拷貝操作更高效

總結

復制帶隨機指針的鏈表是考察對鏈表結構和哈希表應用的經典題目。兩種主要解法各有優劣：

• 面試推薦：通常優先解釋哈希表法，然后根據面試官要求優化空間復雜度
• 工程實踐：哈希表法更安全可靠，不修改原鏈表結構
• 算法競賽：可能更傾向空間優化的穿插法

掌握這道題有助于理解更復雜的鏈表操作和對象引用關系，是數據結構學習中的重要里程碑。 “`

這篇文章共計約1700字，涵蓋了問題描述、解決方案、復雜度分析、邊界情況、測試用例、方法比較和擴展思考等內容，采用Markdown格式編寫，可直接用于技術博客或面試準備。