剑指offer - 复杂链表的复制 - JavaScript

题目描述:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的 head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的 head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

思路

用一个哈希表表示映射关系:键是原节点,值是复制的节点。

整体算法流程是:

  • 第一次遍历,复制每个节点和 next 指针,并且保存“原节点-复制节点”的映射关系
  • 第二次遍历,通过哈希表获得节点对应的复制节点,更新 random 指针

代码实现

使用 ES6 的Map,可以直接将对象作为键值。

JavaScript 代码实现:

// ac地址:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
// 原文地址:https://xxoo521.com/2020-02-05-link-copy/

/**
 * // 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;
    }
    const map = new Map();
    let node = head; // 当前节点
    const newHead = new Node(node.val);
    let newNode = newHead; // 当前节点的copy
    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;
};

更多资料

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×