[/dsa/leetcode]

138 - Copy List with Random Pointer

Friday, 18 September 2026

<medium> [problem]

Copying the nodes is the easy half; the real problem is needing a correspondence from each old node to its copy, kept either in a hash map or woven into the list itself.

{linked list}{hash table}

Problem

A linked list of length n is given where each node contains an additional random pointer, which may point to any node in the list or be null. Construct a deep copy: n brand new nodes whose next and random pointers point only at nodes in the copied list, never at the original.

Nodes are shown as [val, random_index], where the index is the position the random points at.

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • random is null or points at some node in the list

Approach

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> clone;
        Node dummy(0);
        Node* tail = &dummy;
        Node* curr = head;
        while (curr) {
            Node* newnode = new Node(curr->val);
            clone[curr] = newnode;
            tail->next = newnode;
            tail = tail->next;
            curr = curr->next;
        }
        curr = head;
        while (curr) {
            clone[curr]->random = curr->random ? clone[curr->random] : nullptr;
            curr = curr->next;
        }
        return dummy.next;
    }
};
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;

        Node* curr = head;
        while (curr) {
            Node* copy = new Node(curr->val);
            copy->next = curr->next;
            curr->next = copy;
            curr = copy->next;
        }

        curr = head;
        while (curr) {
            curr->next->random = curr->random ? curr->random->next : nullptr;
            curr = curr->next->next;
        }

        Node* newhead = head->next;
        curr = head;
        while (curr) {
            Node* copy = curr->next;
            curr->next = copy->next;
            copy->next = curr->next ? curr->next->next : nullptr;
            curr = curr->next;
        }
        return newhead;
    }
};
  • time: O(n) - three passes
  • space: O(1) - no structure beyond the copied nodes themselves
quantinium © 2026