###### tags: `Leetcode` `medium` `hash` `list` `python` `Top 100 Liked Questions`

# 138. Copy List with Random Pointer

## [題目連結:]https://leetcode.com/problems/copy-list-with-random-pointer/

## 題目:
A linked list of length ```n``` is given such that each node contains an additional random pointer, which could point to any node in the list, or ```null```.

Construct a ```deep copy``` of the list. The deep copy should consist of exactly ```n``` **brand new** nodes, where each new node has its value set to the value of its corresponding original node. Both the ```next and random``` pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. **None of the pointers in the new list should point to nodes in the original list**.

For example, if there are two nodes ```X``` and ```Y``` in the original list, where ```X.random --> Y```, then for the corresponding two nodes ```x``` and ```y``` in the copied list, ```x.random --> y```.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of ```n``` nodes. Each node is represented as a pair of ```[val, random_index]``` where:

* ```val```: an integer representing ```Node.val```
* ```random_index```: the index of the node (range from ```0 to n-1```) that the ```random``` pointer points to, or ```null``` if it does not point to any node.

Your code will **only** be given the ```head``` of the original linked list.


#### [圖片來源:] https://leetcode.com/problems/copy-list-with-random-pointer/

## 解題想法:
* 給一個Linked list，每個node有個額外pointer random，求該list的深層copy
* pointer **random**，
* 其作用為指向隨機的任何一個node
* 也可以為nullptr

input:head = [[7,None],[13,0],[11,4],[10,2],[1,0]]

ex: [13,0]
'13'表示Node 
'0'表示指向第0個node 即 Node(7) 
但random的資料型態也是Node  input給數字表示指向的位置

* 可以參考[133. Clone Graph](/SCsvgf4HTOyU5mQ3C1-daA)相同概念
* 使用字典存已clone的資訊
* key為原node
* val為cloneNode
* nodeMap={None: None}
* 一開始要給一組None:None(用已表示list尾巴)

## Python:

class Node:
    #random的資料型態也是Node
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
        
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        #key為原node val為cloneNode
        nodeMap={None: None} #一開始要給一組None:None(如圖尾)
        return self.dfs(head,nodeMap)
    def dfs(self,head,nodeMap):
        if head in nodeMap:
            #若已紀錄，則表示該head已經有拷貝了，返回拷貝的head
            return nodeMap[head]
        cloneNode=Node(head.val)
        nodeMap[head]=cloneNode
        #遞迴求next與random
        cloneNode.next=self.dfs(head.next,nodeMap)
        cloneNode.random=self.dfs(head.random,nodeMap)
        return cloneNode