Copy list with random pointer

Back to index

From the LeetCode problem with the same name. In this problem we are asked to construct a deep copy of a linked list that has a little additional structure. The additional structure is that every node has – in addition to the next pointer – a 'random' pointer that points to some other node.

It can be complex if we mix up the creation of new nodes and the adding of pointers. So one strategy to create the deep copy is to first create a 'blank' copy in which we clone each of the nodes and keep track of the bijection between the new nodes and the old nodes with a HashMap. Then we can safely copy all of the structure by iterating over the original list and making links to the appropriate new node that we can look up with our HashMap.

class Solution {
  public Node copyRandomList(Node head) {
    if (head == null) {
      return null;
    }

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

    Node current = head;

    while (current != null) {
      Node newCurrent = new Node(current.val);
      old2New.put(current, newCurrent);
      current = current.next;
    }

    current = head;    
    while (current != null) {
      Node newCurrent = old2New.get(current);
      if (current.next != null) {
        newCurrent.next = old2New.get(current.next);
      }

      if (current.random != null) {
        newCurrent.random = old2New.get(current.random);
      }

      current = current.next;
    }

    return old2New.get(head);
  }
}