Copy List with Random Pointer - Practice Coding Problems

Copy List with Random Pointer - Problem

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Input & Output

Example 1 — Basic List with Random Pointers

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

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

💡 Note: Node 0 (value 7) has no random pointer. Node 1 (value 13) points to node 0. Node 2 (value 11) points to node 4. Node 3 (value 10) points to node 2. Node 4 (value 1) points to node 0.

Example 2 — Simple Two-Node List

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

› Output: [[1,1],[2,1]]

💡 Note: Both nodes point to the second node (index 1). The deep copy preserves these relationships.

Example 3 — Empty List

$ Input: head = []

› Output: []

💡 Note: Empty list returns empty list.

Constraints

0 ≤ n ≤ 1000
-10⁴ ≤ Node.val ≤ 10⁴
Node.random is null or is pointing to some node in the linked list.

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list with next and random pointers

Deep Copy

Create new nodes with same structure

Output

Independent copy with preserved relationships

Key Takeaway

🎯 Key Insight: The challenge is maintaining the mapping between original and new nodes to correctly set random pointers

Asked in

A Amazon 45 M Microsoft 38 G Google 32 F Facebook 28

The key insight is maintaining a mapping between original and copied nodes to preserve pointer relationships. The two-pass hash map approach is most intuitive while the interweaving approach achieves O(1) space. Time: O(n), Space: O(1) for optimal solution.

Common Approaches

Approach	Time	Space	Notes
✓ Interweaving Approach	O(n)	O(1)	Create new nodes interweaved with original nodes, then separate them
Two-Pass Hash Map	O(n)	O(n)	Create all nodes first, then set all pointers using a hash map

Interweaving Approach — Algorithm Steps

Insert new nodes after each original node
Set random pointers using the interweaved structure
Extract and separate the new list

Visualization

Tap to expand

Step-by-Step Walkthrough

Interweave

Insert new nodes between original nodes

Connect Random

Set random pointers using interweaved structure

Separate

Extract the new list while restoring original

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    int val;
    struct Node* next;
    struct Node* random;
};

struct Node* solution(struct Node* head) {
    if (!head) return NULL;
    
    // Step 1: Create new nodes and interweave with original
    struct Node* current = head;
    while (current) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->val = current->val;
        newNode->next = current->next;
        newNode->random = NULL;
        current->next = newNode;
        current = newNode->next;
    }
    
    // Step 2: Set random pointers for new nodes
    current = head;
    while (current) {
        if (current->random) {
            current->next->random = current->random->next;
        }
        current = current->next->next;
    }
    
    // Step 3: Separate the two lists
    struct Node* newHead = head->next;
    struct Node* currentOld = head;
    struct Node* currentNew = newHead;
    
    while (currentOld) {
        currentOld->next = currentOld->next ? currentOld->next->next : NULL;
        currentNew->next = currentNew->next ? currentNew->next->next : NULL;
        currentOld = currentOld->next;
        currentNew = currentNew->next;
    }
    
    return newHead;
}

int main() {
    // Simplified main for demonstration
    printf("[]");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Three passes through the list, each taking O(n) time

✓ Linear Growth

Space Complexity

O(1)

Only creates the required new nodes, no extra hash map

✓ Linear Space

89.4K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Interweaving Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler