medium Copy List with Random Pointer

Problem Statement

You are given a linked list where each node contains an additional random pointer. This pointer could point to any node in the list or be null.

Create a deep copy of this linked list. The deep copy should have n new nodes, where each new node's value matches the value of its corresponding node in the original list. Additionally, both the next and random pointers of the new nodes should point to the new nodes in the copied list.

The pointers in the copied list should maintain the same structure as the original list. None of the pointers in the new list should reference any node in the original list.

For instance, if in the original list, node X has a random pointer to node Y (X.random -> Y), then in the copied list, the corresponding nodes x and y should have a random pointer such that x.random -> y.

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

val: It is an integer representing Node.val
randomIndex: 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.

Given a head of the linked list, return the head of the newly copied linked list.

Examples

Example 1:

Input: head = [[3, 1], [4, null], [5, 0], [7, 2]]

Output: [[3, 1], [4, null], [5, 0], [7, 2]]
Explanation: The original list is cloned and returned.

Example 2:

Input: head = [[1, 2], [2, 0], [3, 1]]

Expected Output: [[1, 2], [2, 0], [3, 1]]
Explanation: The original list is cloned and returned.

Example 3:

Input: head = [[8, 2], [9, null], [7, 1]]

Output: [[8, 2], [9, null], [7, 1]]
Explanation: The original list is cloned and returned.

Constraints:

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

Try it yourself

Try solving this question here:

✅ Solution Copy List with Random Pointer

Problem Statement

You are given a linked list where each node contains an additional random pointer. This pointer could point to any node in the list or be null.

The pointers in the copied list should maintain the same structure as the original list. None of the pointers in the new list should reference any node in the original 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, randomIndex] where:

val: It is an integer representing Node.val
randomIndex: 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.

Given a head of the linked list, return the head of the newly copied linked list.

Examples

Example 1:

Input: head = [[3, 1], [4, null], [5, 0], [7, 2]]

Output: [[3, 1], [4, null], [5, 0], [7, 2]]
Explanation: The original list is cloned and returned.

Example 2:

Input: head = [[1, 2], [2, 0], [3, 1]]

Expected Output: [[1, 2], [2, 0], [3, 1]]
Explanation: The original list is cloned and returned.

Example 3:

Input: head = [[8, 2], [9, null], [7, 1]]

Output: [[8, 2], [9, null], [7, 1]]
Explanation: The original list is cloned and returned.

Constraints:

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

Solution

To solve this problem, we make three passes over the original linked list to create a deep copy that maintains the same next and random pointer structure as the original list. In the first pass, we insert a copy of each node right next to the original node. This helps us easily link the next pointers of the copied nodes. During the second pass, we set up the random pointers for the copied nodes using the established relationship between the original nodes and their copies. Finally, in the third pass, we separate the original and copied nodes, restoring the original list and forming the deep-copied list.

This approach is efficient because it only traverses the list three times, maintaining a linear time complexity of . The algorithm avoids using extra space by cleverly utilizing the linked list structure to temporarily store the copied nodes next to their originals. This enables us to keep track of the next and random pointers without additional data structures, making the solution space-efficient with extra space.

Step-by-Step Algorithm

Check for Empty List:
- If the input head is null, return null. This handles the edge case where the input list is empty.
First Pass: Create and Insert Copied Nodes:
- Initialize a pointer current to the head of the original list.
- Traverse the list while current is not null:
  - For each node (current), create a new node copy with the same value (current.val).
  - Set the next pointer of copy to current.next.
  - Insert copy right after current by setting current.next to copy.
  - Move current to copy.next (i.e., the next original node).
Second Pass: Set Random Pointers for Copied Nodes:
- Reinitialize current to the head of the original list.
- Traverse the list again while current is not null:
  - If current.random is not null, set the random pointer of current.next (the copied node) to current.random.next (the copy of the node current.random points to).
  - Move current to current.next.next (i.e., the next original node).
Third Pass: Separate the Original and Copied Lists:
- Reinitialize current to the head of the original list.
- Initialize copiedHead to head.next (the head of the copied list).
- Use a pointer copy to iterate over the copied list, initially set to copiedHead.
- Traverse the list while current is not null:
  - Set current.next to current.next.next to restore the original list.
  - If copy.next is not null, set copy.next to copy.next.next to form the copied list. This steps removes the node of the original list.
  - Move both current and copy to their respective next nodes.
Return the Head of the Copied List:
- Return copiedHead, which points to the head of the deep-copied linked list.

Algorithm Walkthrough

Let's walk through the algorithm using the input head = [[3, 1], [4, null], [5, 0], [7, 2]].

Input Linked List:
- Node 1: Value 3, Random Pointer -> Node at index 1 (Node with value 4)
- Node 2: Value 4, Random Pointer -> null
- Node 3: Value 5, Random Pointer -> Node at index 0 (Node with value 3)
- Node 4: Value 7, Random Pointer -> Node at index 2 (Node with value 5)

First Pass: Create and Insert Copied Nodes

Start with current at Node 1 (Value 3):
- Create Node 1' (Value 3).
- Insert Node 1' after Node 1:
  - The list becomes: 3 -> 3' -> 4 -> 5 -> 7.
- Move current to Node 2 (Value 4).
At Node 2 (Value 4):
- Create Node 2' (Value 4).
- Insert Node 2' after Node 2:
  - The list becomes: 3 -> 3' -> 4 -> 4' -> 5 -> 7.
- Move current to Node 3 (Value 5).
At Node 3 (Value 5):
- Create Node 3' (Value 5).
- Insert Node 3' after Node 3:
  - The list becomes: 3 -> 3' -> 4 -> 4' -> 5 -> 5' -> 7.
- Move current to Node 4 (Value 7).
At Node 4 (Value 7):
- Create Node 4' (Value 7).
- Insert Node 4' after Node 4:
  - The list becomes: 3 -> 3' -> 4 -> 4' -> 5 -> 5' -> 7 -> 7'.
- Move current to null, ending the first pass.

Second Pass: Set Random Pointers for Copied Nodes

Start with current at Node 1 (Value 3):
- current.random points to Node 2 (Value 4).
- Set Node 1'.random to Node 2'.random:
  - Node 3'.random is now correctly set to Node 2'.
- Move current to Node 2 (Value 4).
At Node 2 (Value 4):
- current.random is null.
- Node 2'.random remains null.
- Move current to Node 3 (Value 5).
At Node 3 (Value 5):
- current.random points to Node 1 (Value 3).
- Set Node 3'.random to Node 1'.random:
  - Node 3'.random is now correctly set to Node 1'.
- Move current to Node 4 (Value 7).
At Node 4 (Value 7):
- current.random points to Node 3 (Value 5).
- Set Node 4'.random to Node 3'.random:
  - Node 4'.random is now correctly set to Node 3'.
- Move current to null, ending the second pass.

Third Pass: Separate the Original and Copied Lists

Start with current at Node 1 (Value 3), copiedHead at Node 1' (Value 3), and copy at Node 1'.
- Set current.next to Node 2 (restoring the original list).
- Set copy.next to Node 2'.
- Move current to Node 2 and copy to Node 2'.
At Node 2 (Value 4):
- Set current.next to Node 3 (restoring the original list).
- Set copy.next to Node 3'.
- Move current to Node 3 and copy to Node 3'.
At Node 3 (Value 5):
- Set current.next to Node 4 (restoring the original list).
- Set copy.next to Node 4'.
- Move current to Node 4 and copy to Node 4'.
At Node 4 (Value 7):
- Set current.next to null (restoring the original list).
- Set copy.next to null.
- Move current to null and copy to null, ending the third pass.

Final Output

Copied List:
- 3' -> 4' -> 5' -> 7', with correct next and random pointers.
Original List remains unchanged:
- 3 -> 4 -> 5 -> 7.

Code

java

// Definition for a ListNode in the linked list
// class ListNode {
//     int val;
//     ListNode next;
//     ListNode random;

//     public ListNode(int val) {
//         this.val = val;
//         this.next = null;
//         this.random = null;
//     }
// }

public class Solution {
    // Method to create a deep copy of a linked list with random pointers
    public ListNode copyRandomList(ListNode head) {
        if (head == null) return null;  // If the original list is empty, return null

        // Step 1: Create the copied nodes and insert them next to their originals
        ListNode current = head;
        while (current != null) {
            ListNode copy = new ListNode(current.val);  // Create a new node (deep copy)
            // original linked list: A->B->C.
            // Updated linked list A->A'->B->B'->C->C.
            copy.next = current.next;           // Set the next of the new node
            current.next = copy;                // Link the new node after the original node
            current = copy.next;                // Move to the next original node
        }

        // Step 2: Assign random pointers for the copied nodes
        current = head;
        while (current != null) {
            if (current.random != null) { 
                current.next.random = current.random.next;  // Set the random pointer for the copied node
            }
            current = current.next.next;  // Move to the next original node
        }

        // Step 3: Separate the original list from the copied list
                // i.e. A->A'->B->B'->C->C' would be broken to A->B->C and A'->B'->C'
        current = head;
        ListNode copiedHead = head.next;  // Head of the copied linked list
        ListNode copy = copiedHead;
        while (current != null) {
            current.next = current.next.next;  // Restore the original list
            if (copy.next != null) {
                copy.next = copy.next.next;    // Set the next for the copied list
            }
            current = current.next;  // Move to the next original node
            copy = copy.next;        // Move to the next copied node
        }

        return copiedHead;  // Return the head of the copied linked list
    }

    // Helper method to print the list for testing
    public void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            int randomVal = (current.random != null) ? current.random.val : -1;  // Get the random value or -1 if null
            System.out.print("ListNode value: " + current.val + ", Random points to: " + randomVal + " | ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // Example 1: Constructing the list [[3, 1], [4, null], [5, 0], [7, 2]]
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(5);
        ListNode node4 = new ListNode(7);
        
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        
        node1.random = node2;  // ListNode with value 3 has a random pointer to node with value 4
        node2.random = null;   // ListNode with value 4 has a random pointer to null
        node3.random = node1;  // ListNode with value 5 has a random pointer to node with value 3
        node4.random = node3;

        // Print the original list
        System.out.println("Original List:");
        solution.printList(node1);

        // Create a deep copy of the list
        ListNode copiedHead = solution.copyRandomList(node1);

        // Print the copied list
        System.out.println("Copied List:");
        solution.printList(copiedHead);
    }
}

Complexity Analysis

Time Complexity

The time complexity of the solution is , where n is the number of nodes in the linked list. This is because we perform three passes over the list:

The first pass creates a copy of each node and inserts it immediately after the original node, taking time.
The second pass sets the random pointers for the copied nodes, which also takes time.
The third pass separates the original and copied lists, which again requires time. Thus, the total time complexity is .

Space Complexity

The space complexity is (excluding the space required for the output). This is because we do not use any extra space proportional to the input size; we only manipulate the existing nodes to achieve the deep copy.

🤖 Don't fully get this? Learn it with Claude

Stuck on Copy List with Random Pointer? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Copy List with Random Pointer** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Copy List with Random Pointer** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Copy List with Random Pointer**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Copy List with Random Pointer**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Verify Preorder Serialization of a Clone Binary Tree With Random Poin →