题目描述

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

提示：

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

测试用例

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

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

思路

• 要找到new链表的random，就要找到cur.random对应的新链表的节点
• 所以要用map存储（原链表节点，新链表节点）
• 这样就可以通过map直接找到curNew.random的位置

代码实现

/**
 * // 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) {
    // 使用map
    // 遍历原链表, 存储源节点和复制节点
    if(!head){
        return null;
    }
    let map = new Map();
    const newHead = new Node(head.val);
    let cur = head;
    let curNew = newHead;
    map.set(cur, curNew);

    while(cur.next){
        curNew.next = new Node(cur.next.val);
        cur = cur.next;
        curNew = curNew.next;
        map.set(cur, curNew);
    }
    // console.log("map: ", map);
    cur = head;
    curNew = newHead;
    // 要找到new链表的random，就要cur.random对应的新链表的节点
    // 所以要用map存储（原链表节点，新链表节点） 
    // 这样就可以通过map直接找到curNew.random的位置
    while(curNew){
        // console.log("cur.random: ", cur.random);
        if(!cur.random){
            curNew.random = null;
        }
        else{
            curNew.random = map.get(cur.random);
        }
        curNew = curNew.next;
        cur = cur.next;
    }
    return newHead;
};