Copy list with random pointer

Hash Table Linked List

62.4% acceptance

Jan 13, 2026

15455

1675

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.

Solution

C++

Time O(n)

Space O(1)

LeetCode

solution.cpp

class Solution {
public:
  Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    unordered_map<Node*, Node*> map;
    Node* curr = head;
    while (curr) {
      map[curr] = new Node(curr->val);
      curr = curr->next;
    }
    curr = head;
    while (curr) {
      if (curr->next) map[curr]->next = map[curr->next];
      if (curr->random) map[curr]->random = map[curr->random];
      curr = curr->next;
    }
    return map[head];
  }
};