> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/138.-copy-list-with-random-pointer.md).

# 138. Copy List with Random Pointer

## 1.問題

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

![](/files/-LNYHcLn2Il4gyKemcG-)

## 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;
    }
};
```