Copy List With Random Pointer

Asked byFacebookAmazonMicrosoftBloombergGoogleApple

Problem

Given a linked list where each node has an additional random pointer that can point to any node in the list or to null, return a deep copy of the list — a completely new set of nodes with the same values and the same relative next/random structure.

Examples

Example 1

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

Output:a deep-copied list with the same next/random structure

Each pair is [value, index of the node its random pointer targets, or null].

Constraints

0 <= n <= 1000

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Linked List pattern

A chain of nodes, each pointing to the next. No random access like an array, but insertion and deletion at a known position is O(1), and many classic problems come down to careful pointer rewiring.

Look for this pattern when

The problem explicitly gives you a linked list (reverse it, merge lists, detect a cycle, reorder it).
You need O(1) insertion/deletion without shifting elements, unlike an array.

Read the full Linked List guide →

Video walkthroughs

Original problem on LeetCode ↗