> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](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).

# 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 %}