Copy List With Random Pointer

Problem Summary

A linked list where each node has a val, a next pointer, and a random pointer that can point to any node in the list or null. Return a deep copy of the list — every node must be a new object, with the same val, next, and random structure as the original.

Constraints:

The list has between 0 and 1,000 nodes.
Node values are integers in the range [-10,000, 10,000].
random may point to any node or be null.

Techniques

Hash Table
Linked List

Solution

class _Node {
    val: number
    next: _Node | null
    random: _Node | null

    constructor(val?: number, next?: _Node, random?: _Node) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
        this.random = (random===undefined ? null : random)
    }
}

function copyRandomList(head: _Node | null): _Node | null {
    let nodes = new Map<_Node, _Node>() 
    let currentOld: _Node | null = head

    while (currentOld) {
        nodes.set(currentOld, new _Node(currentOld.val))
        currentOld = currentOld.next
    }
    
    currentOld = head

    while (currentOld) {
        let newNode: _Node = nodes.get(currentOld)!

        if(currentOld.random) {
            newNode.random = nodes.get(currentOld.random)!
        }

        if (currentOld.next) {
            newNode.next = nodes.get(currentOld.next)!
        }

        currentOld = currentOld.next
    }

    return nodes.get(head!)!
};