Leetcode 138 - Copy List with Random Pointer

題目

Problem#

題目給一個 singly linked list 但是每個 node 除了 val 之外，還有一個 random pointer 指向其他 node
要你回傳 deep copy

想法#

用 dictionary 把舊的 node 映射到新的 node

• 時間複雜度: $\mathcal{O}(n\log{}n)$ (建立 dictionary)
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

• 2023-09-05

賞析#

• 不用另外開空間的作法
  • https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43497/2-clean-C%2B%2B-algorithms-without-using-extra-arrayhash-table.-Algorithms-are-explained-step-by-step.

心得#

跟 133 很像