Start learning free

LESSON 284 OF 348 · LINKED LISTS

Copy List with Random Pointer in TypeScript: O(n) with a Map

Practice O(n) Read the full explanation

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.

 

Example 1:

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

Example 2:

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

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.

 

Constraints:

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

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.


STEP 1 OF 11
    Ctrl + Enter to check

    TYPESCRIPT · LINKED LISTS

    Copy List Random Pointer in TypeScript, explained

    Problem overview

    Each node of the list has a val, a next pointer and a random pointer. The random pointer can point at any node of the same list, including the node itself, or at null. The method copyRandomList receives the head and must return the head of a deep copy: exactly n brand new nodes with the same values, where both next and random of the new nodes point to new nodes. Nothing in the copy may point back into the original list.

    The input is written as pairs [val, random_index]. In [[1, 1], [2, 1]], the first node has the value 1 and its random pointer goes to index 1, the second node. The second node's random pointer also goes to index 1, so it points at itself. The copy has the same shape, built from new nodes. An empty list gives null.

    Approach: a map from each original to its copy

    Copying the values and the next chain is easy: walk the list and build new nodes one by one. The hard part is random. When you create a copy of node A, its random target may be a node further down the list, one that has no copy yet. And a random pointer may also point backwards, to a node you copied earlier, but you have lost track of which copy that was.

    The standard answer is to split the job in two passes with a lookup table from each original node to its copy:

    1. Pass one creates one copy per original node, carrying only the value, and records the pair in the table.
    2. Pass two visits every original node again. All copies now exist, so for any original node, the copy of node.next and the copy of node.random are one lookup away. Use them to wire the copy.

    The table needs the node objects themselves as keys. That is what a Map allows. A plain object would not work here: object keys are turned into strings, and every node becomes "[object Object]", so all nodes would share one entry.

    This takes O(n) time and O(n) extra space, which is what the statement allows. The idea is easy to get right, and a later lesson on the same problem removes the table.

    Step by step

    1. Create an empty Map named copies. Its keys are original nodes and its values are their copies.
    2. Declare the walking variable node with let and start it at head. The head itself stays untouched, because the second pass and the return both need it.
    3. Loop while node is truthy for the first pass, so every original node is visited.
    4. Store a new ListNode built from node.val in the map, keyed by node. Only the value is copied now. The copy's links come later, when every copy exists.
    5. Advance node to node.next. Without this the loop never ends.
    6. Reset node to head, since the first loop left it at null.
    7. Start a second loop with the same condition. Now every original has a copy in the map.
    8. Wire next: set the copy's next to the copy of node.next. For the last node, node.next is null, which has no entry, so get returns undefined and || null turns that into null.
    9. Wire random the same way, with node.random as the key.
    10. Advance node along the original list's next links. The copies' links are what this loop is building.
    11. Return copies.get(head) || null. For an empty list, head is null, the lookup gives undefined, and the fallback makes the answer null.

    The solution in TypeScript

    class Solution {
    copyRandomList(head: ListNode | null): ListNode | null {
        let copies = new Map<ListNode, ListNode>();
        let node = head;
        while (node) {
            copies.set(node, new ListNode(node.val));
            node = node.next;
        }
        node = head;
        while (node) {
            copies.get(node).next = copies.get(node.next) || null;
            copies.get(node).random = copies.get(node.random) || null;
            node = node.next;
        }
        return copies.get(head) || null;
    }
}

    The TypeScript details worth knowing:

    • Type arguments. new Map<ListNode, ListNode>() says the keys are nodes and the values are nodes. An empty map gives the compiler nothing to infer from, so the arguments are written out. They are checked by the compiler only. When TypeScript compiles to JavaScript they are erased, and the map at run time is an ordinary Map.
    • get and missing keys. Map.prototype.get returns undefined when the key is absent. Looking up null is allowed and just finds nothing. The pointers in the copy must be null, not undefined, so the code adds || null. The expression ?? null works too and says "only for undefined or null".
    • Keys are compared by identity. Two different nodes holding the same value are two different keys. This matters for [[3, null], [3, 0], [3, null]], where all three nodes have the value 3 but get three separate copies.
    • Reassigning node. let node = head gives node the type ListNode | null. After the first loop it is null, which is why it has to be reset to head.

    Complexity

    Time: O(n). Each of the two passes visits every node once. Map operations with object keys take constant time on average.

    Space: O(n). The map holds one entry per node. The copy itself is also n nodes, but that is the required output, not extra working space.

    Edge cases and common mistakes

    • An empty list. head is null, both loops are skipped, and the method returns null.
    • A random pointer to itself. In [[1, 1], [2, 1]], the second node's copy points at itself, not at the original second node. The map lookup does that correctly.
    • Random pointers going backwards or forwards. Both are handled, because the second pass starts only after every copy exists.
    • Equal values. The map is keyed by node, not by value. A table keyed by val would merge the three nodes in [[3, null], [3, 0], [3, null]].
    • A plain object as the table. Every node turns into the same string key, so the entries overwrite one another.
    • Pointing into the original. Writing node.random directly into the copy would satisfy a value check but would break the rule that no pointer of the copy leads to the original list.
    • Returning a copy with undefined links. Skipping || null would leave undefined in the last node's next and in every null random.

    Testing

    • [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] gives the same shape, with all new nodes.
    • [[1, 1], [2, 1]] gives [[1, 1], [2, 1]].
    • [[3, null], [3, 0], [3, null]] gives [[3, null], [3, 0], [3, null]].
    • An empty list gives null.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free