Workspace

Problem workspace

3 day streakD

Copy a List with Random Pointers

MediumLinked ListsConstruction

The challenge

Deep-copy an acyclic next chain whose nodes also have arbitrary random pointers.

Each random pointer is null or refers to a node in the same next chain. The input remains unchanged.

Example

A random link from original A to original C becomes copy A → copy C, never a link into the original.

Use the walkthrough below to inspect the input and each state change.

See Copy random pointers, step by step

Follow the pointers. Watch each link change.

4 nodes · singly linkedIDs = node identity · ∅ = null
Forward, backward and null: Read the inputIDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links. Node positions stay fixed while arrows change. The pointer strip and node table below give the same state in text.head7A113A211A310A4∅
CurrentResultYellow arrow: changed next linkDashed arrow: random link
headA1
Inspect node links
Each row is a distinct node object. D is the dummy sentinel.
NodeValueNextRandom
A17A2null
A213A3A1
A311A4A4
A410nullA2
Step 01 / 10

Read the input

IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.

Start from the input head pointers.
View original input

A: 7 (A1) → 13 (A2) → 11 (A3) → 10 (A4); parameters: {"random":[null,0,3,1]}

Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.

Put it into code

Allocate every clone first so even forward and self random links already have a destination.

Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        self.random = None


def copy_random(head):
    copies = {None: None}
    curr = head
    while curr:
        copies[curr] = Node(curr.val)
        curr = curr.next
    curr = head
    while curr:
        copies[curr].next = copies[curr.next]
        copies[curr].random = copies[curr.random]
        curr = curr.next
    return copies[head]

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap