Deep Copy a Random-Pointer Linked List

medium linked list hash map

Problem

Each node has a value, a next pointer, and a random pointer that may point anywhere in the list (or be null). Build an independent deep copy. The simplest approach: in pass one, walk the list and create a clone of every node, storing the original-to-clone mapping in a hash map. In pass two, walk again and wire each clone's next and random by looking up the originals' targets in the map.

Input[7|null, 13|0, 11|4, 10|2, 1|0]

Outputindependent copy with same shape

Each pair is "value | random index" (or null).

list ("val|randomIdx" pairs, ';' separated; '_' for null random)

def copy_random_list(head):
    mapping = {}
    p = head
    while p:
        mapping[p] = Node(p.val)
        p = p.next
    p = head
    while p:
        c = mapping[p]
        c.next = mapping[p.next] if p.next else None
        c.random = mapping[p.random] if p.random else None
        p = p.next
    return mapping[head] if head else None

function copyRandomList(head) {
  const map = new Map();
  let p = head;
  while (p) {
    map.set(p, { val: p.val, next: null, random: null });
    p = p.next;
  }
  p = head;
  while (p) {
    const c = map.get(p);
    c.next = p.next ? map.get(p.next) : null;
    c.random = p.random ? map.get(p.random) : null;
    p = p.next;
  }
  return head ? map.get(head) : null;
}

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        for (Node p = head; p != null; p = p.next) map.put(p, new Node(p.val));
        for (Node p = head; p != null; p = p.next) {
            Node c = map.get(p);
            c.next = p.next == null ? null : map.get(p.next);
            c.random = p.random == null ? null : map.get(p.random);
        }
        return head == null ? null : map.get(head);
    }
}

Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> m;
    for (Node* p = head; p; p = p->next) m[p] = new Node(p->val);
    for (Node* p = head; p; p = p->next) {
        Node* c = m[p];
        c->next = p->next ? m[p->next] : nullptr;
        c->random = p->random ? m[p->random] : nullptr;
    }
    return head ? m[head] : nullptr;
}

Time: O(n) Space: O(n)