**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.

**Challenge**

Could you solve it with O(1) space?

## Solution1: O(n) space, using HashMap put save (node, new node) pairs

public RandomListNode copyRandomList(RandomListNode head) { //O(n) space version, using hashMap if (head == null) { return null; } Map<RandomListNode, RandomListNode> map = new HashMap<>(); RandomListNode runner = head; RandomListNode headCopy = new RandomListNode(head.label); map.put(head, headCopy); RandomListNode copyRunner = headCopy; //deep copy nodes and next pointers while (runner.next != null) { copyRunner.next = new RandomListNode(runner.next.label); runner = runner.next; copyRunner = copyRunner.next; map.put(runner, copyRunner); } //deep copy random pointers for (RandomListNode node : map.keySet()) { map.get(node).random = map.get(node.random); } return headCopy; }

Solution2: O(1) space