# 138. Copy List with Random Pointer (Medium)

https://leetcode.com/problems/copy-list-with-random-pointer/

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.

Example 1:

```Input:
{"\$id":"1","next":{"\$id":"2","next":null,"random":{"\$ref":"2"},"val":2},"random":{"\$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
```

Note:

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

## Solutions

``````class Solution {

// The description of this problem is vague and the first response for it is simple, but why
// tagged as medium difficulty?

// I think the most most difficult part is the circles formed by the random link. We need to keep
// track of the visited nodes to avoid deadlock. Also, there may be some independent nodes that

Map<Node, Node> nodeMap = new HashMap<>();

}

public Node recurse(Node head, Map<Node, Node> visited) {
return null;
}

}

Node copy = new Node(head.val, null, null);

return copy;
}
}
``````

## Incorrect Solutions

``````class Solution {

// Incorrect solution.

// The description of this problem is vague and the first response for it is simple, but why
// tagged as medium difficulty?

// I think the most most difficult part is the circles formed by the random link. We need to keep
// track of the visited nodes to avoid deadlock. Also, there may be some independent nodes that

return null;
}

Set<Node> visited = new HashSet<>();

Node copy = new Node(-1, null, null);

return copy;
}

public void recurse(Node head, Node copy, Set<Node> visited) {

// In practice, following null check is not necessary.
return;
}

return;
}

copy.next = new Node(-1, null, null);

}

copy.random = new Node(-1, null, null);