# 138. Copy List with Random Pointer

{% hint style="success" %}

### Key idea: insert copy of each node into original list

### 核心： 把每个点的副本插入原始的list

{% endhint %}

![0, Original list](/files/-LxcYFpP5A6SvXaFr97n)

![1, Copy "next" and "value" into the original list](/files/-LxcYL7fVi2CsYdsLhbX)

![2, Copy "random" ](/files/-LxcYeeIt4E3_pxRPXiZ)

![3, Split original list and copy list, return copy head](/files/-LxcYl7ZvzPqcUwn2ipr)

### Solution:

1. copy next
2. copy random
3. split origin and copy

{% hint style="danger" %}
Don't modify original list when finish copy

Be careful with the case of `current.random == null`
{% endhint %}

{% tabs %}
{% tab title="Java(very efficient)" %}

#### 别忘了最后将orignial list指针next还原

```java
class Solution {
    public Node copyRandomList(Node head) {
        Node dump = new Node(0);
        dump.next = head;
        if(head == null) return null;
        
        // insert new node, copy next
        Node curr = head;
        while(curr != null) {
            Node insert = new Node(curr.val);
            insert.next = curr.next;
            curr.next = insert;
            curr = curr.next.next;
        }
        
        // deep copy random
        curr = head;
        while(curr != null) {
            if(curr.random == null)
                curr.next.random = null;
            else
                curr.next.random = curr.random.next;
            curr = curr.next.next;
        }
        
        // remove original node
        curr = head.next;
        dump.next = curr;
        while(curr.next != null) {
            head.next = head.next.next;
            curr.next = curr.next.next;
            head = head.next;
            curr = curr.next;
        }
        // add tail
        head.next = null;
        curr.next = null;
        
        return dump.next;
    }
}
```

{% endtab %}

{% tab title="Python" %}

```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 copyRandomList(self, head: 'Node') -> 'Node':
        # ege case
        if head == None:
            return None
        
        # regular case
        self.copyNext(head)
        self.copyRandom(head)
        return self.split(head)
        
    
    def copyNext(self, head):
        while head != None:
            temp = ListNode(head.val)
            temp.next = head.next
            head.next = temp
            head = head.next.next
            
    def copyRandom(self, head):
        while head != None:
            if head.random != None:
                head.next.random = head.random.next
            else:
                head.next.random = None
            head = head.next.next
            
    def split(self, head):
        dummy = ListNode(0)
        head = head.next
        dummy.next = head
        while head.next != None:
            head.next = head.next.next
            head = head.next
        return dummy.next
```

{% endtab %}
{% endtabs %}

{% hint style="danger" %}
在split步骤时，在head指针挪动时，每次应该只移动一步`head = head.next`，因上面一步已经将`head.next`指向了`head.next.next`.
{% endhint %}


---

# 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://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/vi.-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.