Reference: LeetCode
Difficulty: Medium

## Problem

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 of the list.

Note: You must return the copy of the given head as a reference to the cloned list.

Example:

## Analysis

### Iteration

Just create the new nodes in the first pass. Don’t do anything else.

Note: map.get(null) will return null.

Time: $O(N)$
Space: $O(N)$

### Recursion

Time: $O(N)$
Space: $O(N)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.