複製客製化鏈結串列 Copy List w/ Random Pointer_Leetcode #138

JJ Ying on Unsplash

題目敘述

題目會給定一個帶有Random Pointer的鏈結串列，要求我們實體複製deep copy這條鏈結串列，並且輸出副本的根結點。

註:
傳統的Linked list鏈結串列只會有next pointer，題目的客製化鏈結串列除了next pointer之外，還多了一個random pointer，會隨機指向串列中的其他節點。

詳細的題目可在這裡看到

測試範例

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

約束條件

Constraints:

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random is null or is pointing to some node in the linked list.

演算法

先建造一個迴圈，從起始點開始拜訪串列，建立一個字典，以id(node)物件編號為key值，紀錄每個對應的拷貝節點。

接著再建造一個迴圈，從起始點開始拜訪串列，依序補上拷貝節點對應的next pointer 和 randon pointer

最後回傳拷貝串列的起始點，即為所求。

程式碼

class Solution:
　def copyRandomList(self, head: 'Node') -> 'Node':

　　if not head:
　　　return None

　　dict_of_copy = {}

　　cur = head
　　while cur:
　　　dict_of_copy[ id(cur) ] = Node(x=cur.val, next=None, random=None)
　　　cur = cur.next

　　cur = head
　　while cur:

　　　if cur.next:
　　　　dict_of_copy[ id(cur) ].next = dict_of_copy[ id(cur.next) ]

　　　if cur.random:
　　　　dict_of_copy[ id(cur) ].random = dict_of_copy[ id(cur.random) ]

　　　cur = cur.next

　　return dict_of_copy[ id(head) ]

複雜度分析

時間複雜度:

O( n ) 兩輪都是線性掃描，從起始點拜訪到最後一個節點。

空間複雜度:

O( n ) 字典佔用的空間就是備份節點的總數目，剛好和原本的串列一樣長。

關鍵知識點

其實和複製傳統linked list很相似，只是多了一個random pointer要複製。

考量到舊串列和新串列節點的一對一映射關係，聯想到可以用字典dictionary來維護，以id(node)物件編號為鍵值，去儲存對應的拷貝節點。

Reference:

[1] Python O(n) by mirror node 85%+ [w/ Visualization] - Copy List with Random Pointer - LeetCode