题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

示例

 

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

答案1（Map）

/**
 * // 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) {
    let map=new Map;
    let node=head;
    while(node!=null)
    {
        map.set(node,new Node(node.val));//Map.set(key,value)
        node=node.next;
    }
    node=head;
    while(node!=null){
        map.get(node).next=map.get(node.next) === undefined ? null : map.get(node.next);//map.get(key)拿到value
        map.get(node).random=map.get(node.random);
        node=node.next;
    }
    return map.get(head);
};

答案2（拼接+拆分）

/**
 * // 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 node=head;
    //创建新节点
    while(node!=null)
    {
        node.next=new Node(node.val,node.next);
        node=node.next.next;
    }
    //设置新节点的next
    node=head;
    while(node){
        if(node.random!=null){
            node.next.random=node.random.next;
        }
        node=node.next.next;
    }
    node=head;
    let ans=head.next;
    let newnode=head.next;
    while(node.next&&newnode.next)
    {
        node.next=node.next.next;
        newnode.next=newnode.next.next;
        node=node.next;
        newnode=newnode.next;
    }
    node.next=null;
    newnode.next=null;
    return ans;
};