Medium · Linked Lists

Deep copy random pointers

Given the head of a linked list whose nodes each have a next pointer and a random pointer (to any node of the list or null), return a deep copy in which every node is new and every next and random pointer leads to the matching new node. In the samples, next and random are 0-based node indexes (null = no node).

Examples

Example 1

{
  "nodes": [
    {"val": 7, "next": 1, "random": null},
    {"val": 13, "next": 2, "random": 0},
    {"val": 11, "next": 3, "random": 4},
    {"val": 10, "next": 4, "random": 2},
    {"val": 1, "next": null, "random": 0}
  ]
}

Output: copied 5/5

Example 2

{
  "nodes": [
    {"val": 1, "next": 1, "random": 1},
    {"val": 2, "next": 2, "random": 0},
    {"val": 3, "next": null, "random": 2}
  ]
}

Output: copied 3/3

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.