LeetCode——138. 复制带随机指针的链表（借用map实现复制）

LeetCode——138. 复制带随机指针的链表（借用map实现复制）

题目描述

解题思路

本题的特点在于链表的节点不只有next域还有random域，要想对这样的链表进行复制，我们可以先对原链表的值存储在map的value中，key保存为node的地址，这样我们只需要最后对每一个值对应的链表修改其next域和random域即可。

构造一个map数据结构

const map = new Map();

构建一个不包含next和random域的链表

while (node) { map.set(node,new Node(node.val)); node = node.next;}

让node重新指向head

node = head;

依次给map的value赋值next域和random域

while (node) { map.get(node).next = node.next ? map.get(node.next) : null; map.get(node).random = node.random ? map.get(node.random) : null; node = node.next;}

返回map的第一个value就是复制后的链表的头指针。

return map.get(head)

完整AC代码

var copyRandomList = function(head) { let node = head; const map = new Map(); // 首先构建一个不含next和random的链表 while (node) { map.set(node,new Node(node.val)); node = node.next; } node = head; // 重新填写node和random while (node) { map.get(node).next = node.next ? map.get(node.next) : null; map.get(node).random = node.random ? map.get(node.random) : null; node = node.next; } return map.get(head);};

思考

复杂链表的复制看起来挺难的，但是实际上只要能够想到通过map这个数据结构来辅助我们进行复制，便可以极大的降低问题的复杂度，假如不借助map，直接在链表本身进行操作的话，我们不仅要考虑next指针还要考虑random指针，困难程度可想而知，所以能否想到借助map是本题的破题核心。

参考文档

​​剑指Offer——复杂链表的复制（JS实现）​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。