Skip to content

Code:

js
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    function Node(val, next, random) {
        this.val = val;
        this.next = next;
        this.random = random;
    };

    const map = new WeakMap()
    let orginal = head

    while(orginal) {
        map.set(orginal, new Node(orginal.val, null))
        orginal = orginal.next
    }

    orginal = head

    while(orginal) {
        map.get(orginal).next = map.get(orginal.next)
        map.get(orginal).random = map.get(orginal.random)

        orginal = orginal.next
    }

    return map.get(head)
};

// map 映射
// 时间复杂度:O(n)
// 空间复杂度:O(n)


function ArrayToLink (arr = []) {
    function Node(val, next, random) {
        this.val = val;
        this.next = next;
        this.random = random;
    };

    let head = new Node()
    let prev = head

    for (const [val, random] of arr) {
        prev = prev.next = new Node(val, null, random)
    }

    return head.next
}

function LinkToArray (head) {
    let node = head
    const arr = []

    while(node) {
        arr.push([node.val, node.random])

        node = node.next
    }

    return arr
}

console.log((copyRandomList(ArrayToLink([[7,null],[13,0],[11,4],[10,2],[1,0]]))))

❤ With Algorithm