# 138. Copy List with Random Pointer

## 1.問題

* 一個linked list中每個node除了next之外, 有個random指針會隨機指向list中的任一node, 回傳這個list的deep copy

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNY8LpHmVibpDaqlKaN%2F-LNYHcLn2Il4gyKemcG-%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-29%20%E4%B8%8A%E5%8D%8811.03.11.png?alt=media\&token=e821893d-cb01-4f68-9746-8a7195b40a68)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
* function header, parameter
* test input
* 觀察
  * 用map儲存已經複製過的node, 避免重複拷貝, 重複走訪
* 說明想法
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode *, RandomListNode *> m;
        return getCopyNode(head, m);
    }
private:
    RandomListNode * getCopyNode(RandomListNode *head, unordered_map<RandomListNode*, RandomListNode*>& m) {
        if (!head) {
            return NULL;
        }
        if (m.find(head) != m.end()) {
            return m[head];
        }
        
        RandomListNode * node = new RandomListNode(head->label);
        m[head] = node;
        node->next = getCopyNode(head->next, m);
        node->random = getCopyNode(head->random, m);
        return node;
    }
};
```
