# LeetCode 138: Copy List with Random Pointer

## Problem Restatement

We are given the head of a linked list.

Each node contains:

| Field | Meaning |
|---|---|
| `val` | Integer value |
| `next` | Pointer to the next node |
| `random` | Pointer to any node in the list or `None` |

We need to create a deep copy of the entire list.

The copied list must contain entirely new nodes.

Every copied node should preserve:

1. The same `val`
2. The same `next` structure
3. The same `random` structure

But no copied node may point to an original node.

LeetCode describes this as constructing a deep copy where copied nodes replicate both the `next` and `random` relationships of the original list. ([leetcode.com](https://leetcode.com/problems/copy-list-with-random-pointer/?utm_source=chatgpt.com))

## Examples

Example 1:

```text
7 -> 13 -> 11 -> 10 -> 1
```

Suppose:

| Node | Random points to |
|---|---|
| `7` | `None` |
| `13` | `7` |
| `11` | `1` |
| `10` | `11` |
| `1` | `7` |

The copied list must have the same structure:

```text
7' -> 13' -> 11' -> 10' -> 1'
```

and:

| Copied node | Random points to |
|---|---|
| `7'` | `None` |
| `13'` | `7'` |
| `11'` | `1'` |
| `10'` | `11'` |
| `1'` | `7'` |

Every target must be another copied node, not an original node.

Example 2:

```text
1 -> 2
```

with:

```text
1.random -> 2
2.random -> 2
```

The copied structure must preserve those relationships.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head: Optional[Node]` |
| Output | Head of the deep-copied list |
| `next` | Standard linked-list pointer |
| `random` | May point anywhere in the list or `None` |
| Main requirement | Deep copy |

Function shape:

```python
class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        ...
```

## First Thought: Copy Nodes One by One

A first attempt might:

1. Copy each node.
2. Connect copied `next` pointers.
3. Somehow copy `random` pointers later.

The difficulty is:

```text
original.random -> original node
```

must become:

```text
copy.random -> copied node
```

So whenever we see an original node, we must know its corresponding copied node.

This naturally suggests a hash map.

## Key Insight

Store the relationship:

```python
original_node -> copied_node
```

Then:

1. First pass:
   - create all copied nodes
   - fill the map
2. Second pass:
   - connect `next`
   - connect `random`

This guarantees every original node has exactly one copied node.

## Two-Pass Hash Map Algorithm

First pass:

For every original node:

```python
copies[curr] = Node(curr.val)
```

Second pass:

For every original node:

```python
copies[curr].next = copies.get(curr.next)
copies[curr].random = copies.get(curr.random)
```

Finally:

```python
return copies[head]
```

## Why `.get()` Works

The last node has:

```python
curr.next = None
```

Some random pointers are also:

```python
None
```

Using:

```python
copies.get(None)
```

returns:

```python
None
```

which correctly preserves null pointers.

## Correctness

During the first pass, the algorithm creates exactly one copied node for every original node and stores the mapping in `copies`.

Therefore, for every original node `u`, `copies[u]` is the unique copied node corresponding to `u`.

During the second pass:

```python
copies[curr].next = copies.get(curr.next)
```

assigns the copied node corresponding to `curr.next`.

Similarly:

```python
copies[curr].random = copies.get(curr.random)
```

assigns the copied node corresponding to `curr.random`.

Thus, every `next` and `random` relationship from the original list is reproduced exactly between copied nodes.

Since every copied node is newly allocated, no copied node points to an original node. Therefore, the returned list is a correct deep copy.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Two linear passes |
| Space | `O(n)` | Hash map stores all nodes |

## Implementation

```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":
        if head is None:
            return None

        copies = {}

        curr = head

        while curr:
            copies[curr] = Node(curr.val)
            curr = curr.next

        curr = head

        while curr:
            copies[curr].next = copies.get(curr.next)
            copies[curr].random = copies.get(curr.random)
            curr = curr.next

        return copies[head]
```

## Code Explanation

Handle the empty list:

```python
if head is None:
    return None
```

Create the mapping dictionary:

```python
copies = {}
```

The first pass allocates cloned nodes:

```python
while curr:
    copies[curr] = Node(curr.val)
    curr = curr.next
```

At this point:

```text
original node -> copied node
```

exists for every node.

The second pass connects pointers:

```python
copies[curr].next = copies.get(curr.next)
copies[curr].random = copies.get(curr.random)
```

The copied node now points only to copied nodes.

Finally:

```python
return copies[head]
```

returns the copied head.

## O(1) Extra Space Trick

There is also a more advanced solution without a hash map.

The idea:

1. Insert copied nodes directly after original nodes.
2. Use interleaving to connect random pointers.
3. Separate the two lists.

Example:

Before:

```text
A -> B -> C
```

After inserting copies:

```text
A -> A' -> B -> B' -> C -> C'
```

Then:

```python
A'.random = A.random.next
```

because:

```text
A.random.next
```

is the copied version of `A.random`.

Finally, detach the copied list.

This solution uses `O(1)` extra space but is harder to derive.

## O(1) Space Implementation

```python
class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        if head is None:
            return None

        curr = head

        while curr:
            copy = Node(curr.val)
            copy.next = curr.next
            curr.next = copy
            curr = copy.next

        curr = head

        while curr:
            if curr.random:
                curr.next.random = curr.random.next

            curr = curr.next.next

        dummy = Node(0)
        copy_curr = dummy
        curr = head

        while curr:
            copy = curr.next

            curr.next = copy.next
            copy_curr.next = copy

            copy_curr = copy
            curr = curr.next

        return dummy.next
```

## Testing

```python
class Node:
    def __init__(self, x: int, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random

def serialize(head: Node | None):
    nodes = []
    index = {}
    curr = head
    i = 0

    while curr:
        index[curr] = i
        nodes.append(curr)
        curr = curr.next
        i += 1

    result = []

    for node in nodes:
        random_index = (
            index[node.random]
            if node.random is not None
            else None
        )

        result.append([node.val, random_index])

    return result

def run_tests():
    s = Solution()

    n1 = Node(7)
    n2 = Node(13)
    n3 = Node(11)
    n4 = Node(10)
    n5 = Node(1)

    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5

    n1.random = None
    n2.random = n1
    n3.random = n5
    n4.random = n3
    n5.random = n1

    copied = s.copyRandomList(n1)

    assert serialize(copied) == [
        [7, None],
        [13, 0],
        [11, 4],
        [10, 2],
        [1, 0],
    ]

    assert copied is not n1
    assert copied.next is not n2

    single = Node(1)
    single.random = single

    single_copy = s.copyRandomList(single)

    assert single_copy is not single
    assert single_copy.random is single_copy

    assert s.copyRandomList(None) is None

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard multi-node example | Verifies `next` and `random` reconstruction |
| Identity checks | Confirms deep copy |
| Self-random pointer | Node points to itself |
| Empty list | Handles `None` input |