复杂链表的复制

题目

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

思路

1、辅助哈希表

/**
 * // 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 null;

    // 1.复制链表，建立“原节点->新节点”的映射
    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);
    }

    // 2.处理random指针
    newNode = newHead;
    node = head;
    while(newNode) {
        newNode.random = map.get(node.random);
        newNode = newNode.next;
        node = node.next;
    } 
    return newHead;
};

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 null;

    //1.复制一份链表放在前一个节点后面，即根据原始链表的每个节点N创建N,把N直接放在N的next位置，让复制后的链表和原始链表组成新的链表。
    let node = head;
    while(node) {
        let copy = new Node(node.val);
        copy.next = node.next;
        node.next = copy;
        node = node.next.next;
    }

    //2.给复制的链表random赋值，即N.random=N.random.next。
    node = head;
    while(node) {
        if (node.random) {
            node.next.random = node.random.next;
        }
        node = node.next.next;
    }

    //3.拆分链表，将N`和N进行拆分，保证原始链表不受影响。
    let newHead = head.next;
    node = head;
    while(node && node.next) {
        let tmp = node.next;
        node.next = tmp.next;
        node = tmp;
    }

    return newHead;

};

本题难点

在复制链表的过程中构建新链表各节点的 random 引用指向。

考察点

• 链表
• 复杂问题拆解