[LeetCode] 138. Copy List with Random Pointer

轉自LeetCode

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

<Solution>

這題和 Clone Graph 類似，也是 deep copy 的題目

這次要處理的是 link list 中，每個 node 都還有一個 random pointer

random pointer 可以指向任何在 link list 裡的 node，或是 NULL

首先看 recursive 的解法，想法如下

• 先把整個 list copy 完，並在過程中，用 HashMap 記錄每個 node 對應的新 node

• 再處理 random pointer 的部分，如果有值，利用 HashMap 去找對應的 node(O(1))，是 NULL 就直接回傳 NULL

code 如下

也可以改寫成 iterative，想法同上

code 如下

在網路上也看到一個神解

想法如下(圖解請參考這裡)

• 先複製整個 list，每個複製的 node 都插在原 node 的後頭

• 複製 random pointer

• 將原 node 和複製的 node 分解成兩個 link list

code 如下