剑指offer - 复杂链表的复制 - JavaScript
剑指offer - 复杂链表的复制 - JavaScript
心谭博客
发布于 2020-04-21 15:25:27
发布于 2020-04-21 15:25:27
题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 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;
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录