Start learning free

LESSON 285 OF 348 · LINKED LISTS

Copy List with Random Pointer in TypeScript: O(n) Time, O(1) Space

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 O(1) extra space.


STEP 1 OF 22
    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, or at null. The method copyRandomList receives the head and must return the head of a deep copy: exactly n new nodes with the same values, whose next and random pointers lead only to other new nodes. The original list must be left as it was.

    The input is written as pairs [val, random_index]. In [[1, 1], [2, 1]], both random pointers go to the node at index 1. An empty list gives null.

    This version of the lesson adds a budget: O(n) time and only O(1) extra space. The copy itself doesn't count as extra space, but a table from each original to its copy would, and that rules out the usual Map solution.

    Approach: interleave the copies with the originals

    The map solution exists to answer one question: given an original node, where is its copy? The idea here is to make the answer part of the list. Put each copy directly after its original:

    A -> A' -> B -> B' -> C -> C'

    Now the copy of any original X is simply X.next. That gives three passes:

    1. Interleave. After each original node, insert a new node with the same value.
    2. Set the random pointers. For an original node with a random target R, the copy of node is node.next and the copy of R is R.next. So node.next.random = node.random.next.
    3. Separate. Unweave the two lists: restore the originals' next pointers and chain the copies together. The caller's list must be exactly as it was.

    The order matters. Pass two has to come after pass one, since every copy must exist, and before pass three, because the shortcut only works while the copies are still interleaved.

    No extra container is used, only a few variables, so the space is O(1).

    Step by step

    1. Handle the empty list. If head is null, return null. Later code reads head.next, which would fail otherwise.
    2. Start pass one with node at head, and loop while node is truthy.
    3. Save the original successor in nextNode. Inserting the copy overwrites node.next, and without the saved reference the rest of the list would be lost.
    4. Create copyNode with the same value. Its random stays unset for now, since not every copy exists yet.
    5. Splice it in: set node.next = copyNode and copyNode.next = nextNode. The chain continues into the rest of the list. For the last original, nextNode is null, so the last copy ends the chain.
    6. Jump to nextNode, skipping the new copy. Moving to node.next would land on the copy and insert copies of copies forever.
    7. Start pass two from head again. Inside, take copyNode = node.next.
    8. Set the random pointer. If node.random exists, the copy's random pointer becomes node.random.next, which is the copy of the target. If it doesn't, the copy's random stays as the new node was created.
    9. Jump to copyNode.next, the next original, so this pass visits originals only.
    10. Save newHead = head.next, the first copy. Do it before pass three rewires head.next.
    11. Start pass three from head. Take the copy after node, then nextNode, the next original after that copy.
    12. Chain the copies. If nextNode exists, set copyNode.next = nextNode.next, the following copy. For the last pair, the last copy's next is already null.
    13. Restore the original with node.next = nextNode, then advance node to nextNode.
    14. Return newHead.

    The solution in TypeScript

    class Solution {
    copyRandomList(head: ListNode | null): ListNode | null {
        if (!head) {
            return null;
        }

        let node = head;
        while (node) {
            let nextNode = node.next;
            let copyNode = new ListNode(node.val);
            node.next = copyNode;
            copyNode.next = nextNode;
            node = nextNode;
        }

        node = head;
        while (node) {
            let copyNode = node.next;
            if (node.random) {
                copyNode.random = node.random.next;
            }
            node = copyNode.next;
        }

        let newHead = head.next;
        node = head;
        while (node) {
            let copyNode = node.next;
            let nextNode = copyNode.next;
            if (nextNode) {
                copyNode.next = nextNode.next;
            }
            node.next = nextNode;
            node = nextNode;
        }

        return newHead;
    }
}

    The TypeScript details worth knowing:

    • Block-scoped variables. copyNode and nextNode are declared with let inside each loop body, so every pass has its own variables. The same name in three loops is not a clash.
    • Types are only notes. node has the type ListNode from head, yet the loops assign null to it. With strict mode off, the compiler allows this. Types are erased when TypeScript compiles to JavaScript, so the running code only sees objects and null. In strict mode you would write let node: ListNode | null = head and add ! where a node is read after a splice.
    • Truthiness as the loop test. while (node) and if (node.random) work because an object is truthy and null is falsy.
    • New nodes start without a random. A node created from just a value has no random target yet, which is why pass two sets it only when the original has one.

    Complexity

    Time: O(n). Each of the three passes visits each original node once, and each visit does a constant number of pointer assignments.

    Space: O(1) extra. The n new nodes are the required output. Besides them, the code keeps only a handful of variables. The interleaving is temporary and is undone in pass three.

    Edge cases and common mistakes

    • An empty list. The first if returns null before any pointer is read.
    • A single node. The list becomes A, A'. If its random points at itself, pass two sets A'.random = A.next, which is A', a pointer to itself. Pass three separates the nodes.
    • A random pointer to the last node. node.random.next is then the last copy, which exists after pass one.
    • Moving to node.next in pass one. This lands on the copy that was just inserted, so the loop copies its own copies and never ends.
    • Wiring random pointers before the interleaving is complete. The target's copy would not exist yet.
    • Not restoring the original. Leaving the copies woven into the input list changes data the caller owns.
    • Setting the copy's random to node.random. This points into the original list, and the copy must not. The pointer must be node.random.next.
    • Reading head.next too late. Pass three sets head.next back to the second original, so the first copy has to be saved first.

    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