✅剑指 Offer 35. 复杂链表的复制

[Ray-56]

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

[Ray-56]

递归解

var copyRandomList = function(head) {
    const map = new Map();

    function deepClone(node) {
        if (!node) return node;
        if (map.has(node)) return map.get(node);

        const ret = new node();
        map.set(node, ret);
        ret.val = node.val;
        ret.next = deepClone(node.next);
        ret.random = deepClone(node.random);
        return ret;
    }
    return deepClone(head);
};

迭代

var copyRandomList = function(head) {
    if (!head) return null;
    const map = new Map();
    let node = head;
    let newHead = new Node(node.val);
    let newNode = newHead;
    map.set(node, newNode);

    while (node.next) {
        newNode.next = new Node(node.next.val);
        node = node.next;
        newNode = newNode.next;
        map.set(node, newNode)
    }

    newNode = newHead;
    node = head;
    while (newNode) {
        newNode.random = map.get(node.random);
        newNode = newNode.next;
        node = node.next;
    }

    return newHead;
};