> For the complete documentation index, see [llms.txt](https://chunhthanhde.gitbook.io/leetcode-top-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-8-linked-list/060-copy-list-with-random-pointer.md).

# 138. Copy List with Random Pointer 🔗

**Difficulty**: `Medium` - **Tags**: `Linked List`, `Hashing`

[LeetCode Problem Link](https://leetcode.com/problems/copy-list-with-random-pointer/)

***

## Problem Statement 📜

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` pointers of the new nodes should point to new nodes in the copied list, replicating the structure of the original list.

Return the head of the copied linked list.

***

## Examples 🌟

🔹 **Example 1**:

![](https://1796379692-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FXXeIX5WFjwBX14tD3BWy%2Fuploads%2Fgit-blob-7afabbbdc12245c99524c330007661241a1c355b%2Fe1.png?alt=media)

**Input:**

```plaintext
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
```

**Output:**

```plaintext
[[7,null],[13,0],[11,4],[10,2],[1,0]]
```

***

🔹 **Example 2**:

![](https://1796379692-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FXXeIX5WFjwBX14tD3BWy%2Fuploads%2Fgit-blob-b0d1edfbcbe9ddc7b646c76fba882267c63bac70%2Fe2.png?alt=media)

**Input:**

```plaintext
head = [[1,1],[2,1]]
```

**Output:**

```plaintext
[[1,1],[2,1]]
```

***

🔹 **Example 3**:

![](https://1796379692-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FXXeIX5WFjwBX14tD3BWy%2Fuploads%2Fgit-blob-14d6dd4e2fe3d7e741a496dfe2adb0a96374bd72%2Fe3.png?alt=media)

**Input:**

```plaintext
head = [[3,null],[3,0],[3,null]]
```

**Output:**

```plaintext
[[3,null],[3,0],[3,null]]
```

***

## Constraints ⚙️

* The number of nodes in the list is in the range `[0, 1000]`.
* `-10^4 <= Node.val <= 10^4`
* `Node.random` is `null` or points to a node in the list.

***

## Solution 💡

We can solve this problem using **three passes** with a hash map to maintain the original node and its corresponding copied node.

***

### Java Solution

```java
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // Step 1: Create a mapping of original nodes to their copies
        HashMap<Node, Node> map = new HashMap<>();
        Node current = head;

        while (current != null) {
            map.put(current, new Node(current.val));
            current = current.next;
        }

        // Step 2: Set the next and random pointers for the copied nodes
        current = head;
        while (current != null) {
            Node copy = map.get(current);
            copy.next = map.get(current.next); // Link to the copied next node
            copy.random = map.get(current.random); // Link to the copied random node
            current = current.next;
        }

        // Step 3: Return the copied head
        return map.get(head);
    }
}
```

***

## Explanation of the Solution

1. **Mapping Original Nodes to Copies**:
   * Use a hash map to store each original node and its corresponding copied node.
2. **Linking the `next` and `random` Pointers**:
   * Traverse the original list again and set the `next` and `random` pointers of the copied nodes using the hash map.
3. **Returning the Copied Head**:
   * Return the copied node corresponding to the original head from the hash map.

***

## Time Complexity ⏳

* **O(n)**: We traverse the list twice — once to create the nodes and once to set the pointers.

## Space Complexity 💾

* **O(n)**: The hash map stores mappings for `n` nodes.

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%208%20Linked%20List/060%20Copy%20List%20with%20Random%20Pointer/Solution.java).