链接: https://leetcode.cn/problems/copy-list-with-random-pointer/
题意
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
要求深拷贝一个链表,要求链表的random指针也指向正确的结果
解法
做过类似的题目,这边暂时只给出一种简单的解法
使用一个map构建旧节点到新节点的映射
然后两次遍历即可得到复制后的新链表
还有一种解法是将复制后的节点放在原节点之后,然后再将两者分离
这种解法不需要map存储映射关系,空间复杂度更优化
代码
1 | /* |