Skip to content
Hello Python

Copy a Random-Pointer List

Interview ProblemAdvancedMediumArrayHash MapLinked List

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.copyRandomList(records). records[i] is [value, randomIndexOrNone] and next points to i+1. Return newly allocated [value, randomIndexOrNone] records with identical relationships. This serializable contract represents the original random-pointer list.

Starter code

class Solution:
    def copyRandomList(self, records):
        pass
Test cases

mixed-random

{
  "args": [
    [
      [
        7,
        null
      ],
      [
        13,
        0
      ],
      [
        11,
        4
      ],
      [
        10,
        2
      ],
      [
        1,
        0
      ]
    ]
  ]
}

Expected: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Wizard outline
  1. Step 1: Initialize Solution.copyRandomList

    Replace the empty starter with the first real state owned by Solution.copyRandomList. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

  2. Step 2: Pass the Empty case

    Complete the readable core algorithm for one representative Interview case. Allocate every clone before wiring references so forward and backward random pointers both resolve.

  3. Step 3: Harden the Mixed Random boundary

    Repair the reviewed boundary and pass the complete submission contract. The first pass creates one distinct clone position per original. The second pass copies value and the index identifying the same random target, so next-by-order and random relationships are identical while record objects are newly allocated.

Footguns and prerequisites
  • Copy record objects rather than returning the input list or reusing its inner lists.
  • linked lists
  • hashing and sets
Reviewed references
Practice prerequisites
  • Wire Cloned Records(opens in a new tab)

    Wire Cloned Records isolates clone_by_index maps every original position to exactly one new record before any copied relationship is resolved. That focused state discipline is required when implementing copy random pointer records as a complete Interview Problem.

Recommended approach and implementation

Allocate a new two-item record for every source record, then copy each value and random index into its distinct clone record.

Why it works: The first pass creates one distinct clone position per original. The second pass copies value and the index identifying the same random target, so next-by-order and random relationships are identical while record objects are newly allocated.

class Solution:
    def copyRandomList(self, records):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        clones = [[None, None] for _ in records]
        for index, (value, random_index) in enumerate(records):
            clones[index][0] = value
            clones[index][1] = random_index
        return clones