138. 复制带随机指针的链表（JS实现）

以你之姓@ 2023-03-04 08:14 19阅读 0赞

## 1 题目 ##

> 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。  
> 要求返回这个链表的 深拷贝。  
> 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 \[val, random\_index\] 表示：  
> val：一个表示 Node.val 的整数。  
> random\_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 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。  
> 提示：  
> \-10000 <= Node.val <= 10000  
> Node.random 为空（null）或指向链表中的节点。  
> 节点数目不超过 1000 。

## 2 思路 ##

**这道题的主要思路使用一个map，key为原来的节点，value为克隆的节点和指向该原节点的节点数组，在遍历复制的过程中不断更新指针的指向**

## 3代码 ##

/** * // 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) { 
        if (!head) return head;
    
        let linkHead, pre;
    
        const map = new Map();
    
        while(head) { 
            let newNode = new Node(head.val, null, null);
            if (!pre) { 
                linkHead = newNode;
            } else { 
                pre.next = newNode;
            } 
            pre = newNode;
            if (head.random) {     //如果当前节点有随机指针
                let arr = map.get(head.random);
                if (!arr) { 
                    map.set(head.random, [null, newNode]);
                } else { 
                    if (arr[0]) { 
                        newNode.random = arr[0];
                    } else { 
                        arr.push(newNode);
                    }
                }
            }
    
            let currentArr = map.get(head);
            if (currentArr) {     //如果有其他节点指向该克隆的节点
                currentArr[0] = newNode;
                for (let i=1; i<currentArr.length; i++) { 
                    currentArr[i].random = newNode;
                }
            } else { 
                map.set(head, [newNode]);
            }
            head = head.next;
        }
    
        return linkHead;
    };