# Copy List with Random Pointer

## Description

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a [**deep copy**](https://en.wikipedia.org/wiki/Object_copying#Deep_copy) of the 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`) where random pointer points to, or `null` if it does not point to any node.

**Example 1:**

![](https://3217298702-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5BYNv0H5fXhaR-4sW4%2F-M5v2HMzlN2mYAuOPh9_%2F-M5vEDwNIr6nPdVEzQCu%2Fimage.png?alt=media\&token=42ec056b-c4c6-4983-ae93-f9aeb52cc7bd)

> **Input:** head = \[\[7,null],\[13,0],\[11,4],\[10,2],\[1,0]]&#x20;
>
> **Output:** \[\[7,null],\[13,0],\[11,4],\[10,2],\[1,0]]

**Example 2:**

![](https://3217298702-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5BYNv0H5fXhaR-4sW4%2F-M5v2HMzlN2mYAuOPh9_%2F-M5vEFlgDg3bJ-S6Rh1_%2Fimage.png?alt=media\&token=96312c27-317e-490d-b119-2c4a6e2e3b66)

> **Input:** head = \[\[1,1],\[2,1]]&#x20;
>
> **Output:** \[\[1,1],\[2,1]]

**Example 3:**

![](https://3217298702-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5BYNv0H5fXhaR-4sW4%2F-M5v2HMzlN2mYAuOPh9_%2F-M5vEICCNhq-J5b2spTh%2Fimage.png?alt=media\&token=af9e22c3-7305-4a44-8377-a703475719aa)

> **Input:** head = \[\[3,null],\[3,0],\[3,null]]&#x20;
>
> **Output:** \[\[3,null],\[3,0],\[3,null]]

**Example 4:**

> **Input:** head = \[]&#x20;
>
> **Output:** \[]&#x20;
>
> **Explanation:** Given linked list is empty (null pointer), so return null.

**Constraints:**

* `-10000 <= Node.val <= 10000`
* `Node.random` is null or pointing to a node in the linked list.
* Number of Nodes will not exceed 1000.

## **Code**

```java
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node iter = head;
        Node next = null;
        while (iter != null) {
            Node node = new Node(iter.val);
            next = iter.next;
            iter.next = node;
            node.next = next;
            
            iter = next;
        }
        
        iter = head;
        Node randomNext = null;
        while (iter != null) {
            if (iter.random != null) {
                next = iter.next;
                randomNext = iter.random.next;
                next.random = randomNext;
            }
            iter = iter.next.next;
        }
        
        Node result = head.next;
        iter = head.next;
        while (iter != null && iter.next != null) {
            head.next = iter.next;
            iter.next = iter.next.next;
            iter = iter.next;
            head = head.next;
        }
        head.next = null;
        return result;
        
    }
}
```
