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
