# 138. Copy List with Random Pointer

```python
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if head is None:
            return head
        
        dummy = RandomListNode(-1)
        cur = dummy
        curOld = head
        mapping = {}
        mapping[None] = None
        while(curOld):
            cur.next = RandomListNode(curOld.label)
            mapping[curOld] = cur.next
            cur = cur.next
            curOld = curOld.next
            
        cur = dummy
        curOld = head
        while(curOld):
            cur.next.random = mapping[curOld.random] # when random is None, traversing linked list won't add none in the dictionary, we need to do it manually
            cur = cur.next
            curOld = curOld.next
            
        return dummy.next
        '''
```

Use dictionary to map old nodes (as key) to new nodes (as value). So that we could traverse old & new list together and know which new list node should be set as random reference.

```python
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if head is None:
            return head
        
        cur = head
        while(cur):
            nextNode = cur.next
            cur.next = RandomListNode(cur.label) # 5）用前后相邻顺序替代 dictionary 的映射关系，降低额外空间的占用；遇到要优化的算法时，尝试转换思路，什么东西可以【在功能上替代】传统的简单思路
            cur.next.next = nextNode
            cur = nextNode
        
        cur = head    
        while(cur):
            if cur.random: # 1) any next in linked list should be validated;
                cur.next.random = cur.random.next # 2) 如果一边加 random 一边去掉新旧之间的 link，会导致后面的新 node 指前面 新 node 时 找不到了，所以必须用两个循环来处理
            cur = cur.next.next # 3）修改代码时，时刻double check 逻辑是否正确
            
        cur = head
        dummy = RandomListNode(-1)
        newCur = dummy
        while(cur):
            newCur.next = cur.next # 4）跳着连接时，先处理中间值再对前后处理
            cur.next = cur.next.next
            cur = cur.next
            newCur = newCur.next
        
        return dummy.next
        
```

* See 1) 2) 3) 4) 5) in the code comments
* To summary, by inserting new node after old node, we could replace the mapping relationship. The core algorithm is : 

  ```python
  if cur.random: # 1) any next in linked list should be validated;
      cur.next.random = cur.random.next # 2) 如果一边加 random 一边去掉新旧之间的 link，会导致后面的新 node 指前面 新 node 时 找不到了，所以必须用两个循环来处理
  ```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sisyphus.gitbook.io/project/leetcode-notes/linked-list/138.-copy-list-with-random-pointer.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.