> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/lian-biao/138-fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao.md).

# \[138]\[中等]\[哈希表] 复制带随机指针的链表

## 题目描述

[138. 复制带随机指针的链表](https://leetcode-cn.com/problems/copy-list-with-random-pointer/)

## 解题思路

[Leetcode官方题解: 复制带随机指针的链表](https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/)

```python
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def __init__(self):
        self.visited = dict()

    def get_cloned_node(self, node):
        if node is None:
            return None

        if node in self.visited:
            return self.visited[node]
        else:
            self.visited[node] = Node(node.val, None, None)
            return self.visited[node]

    def copyRandomList(self, head: 'Node') -> 'Node':
        if head is None:
            return None

        old_node = head
        new_node = Node(head.val, None, None)
        self.visited[old_node] = new_node

        while old_node:
            new_node.next = self.get_cloned_node(old_node.next)
            new_node.random = self.get_cloned_node(old_node.random)
            old_node = old_node.next
            new_node = new_node.next
        return self.visited[head]
```