Copy List with Random Pointer

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.


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 ( != null) { = new RandomListNode(;
        runner =;
        copyRunner =;
        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


Leave a Reply

Your email address will not be published. Required fields are marked *