Copy List with Random Pointer

medium linked list hash map

Problem

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node.

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;
}

Explanation

Each node has a normal next pointer plus a random pointer that can jump anywhere in the list. The challenge is that when we clone a node, its random target may not exist yet. The fix is a hash map that links every original node to its fresh clone.

In the first pass, we walk the list and create a brand new node for each original, storing the pair original → clone in mapping. We do not wire up any pointers yet — we just make sure every clone exists.

In the second pass, we walk again and, for each original p, look up its clone c. We set c.next to the clone of p.next and c.random to the clone of p.random, both fetched from the map (or None when the original pointer is null).

Because every clone already lives in the map, looking up any random target is instant, no matter where it points. The result is a fully independent deep copy with the same shape.

Example: with nodes [7|null, 13|0, 11|4, 10|2, 1|0], pass one makes five clones; pass two wires each clone's next and points its random at the cloned target index, e.g. node 13's random goes to clone index 0. Two linear passes give O(n) time and O(n) space.

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