Linkedin中如何复制随机指针
这篇文章将为大家详细讲解有关Linkedin中如何复制随机指针，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。
题目描述
给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。
算法分析
深度拷贝一个普通链表的算法非常简单，因为每一个节点只有一个next指针指向下一个节点，整体上是一个线性结构；但是题目中的节点多了一个随机指针，可以指向链表中的任何节点，或者是空的节点。所以在建立新的链表的时候，要考虑到随机指针指向的节点是否已经被新建过了，是否已经存在于新链表中。
1. 需要查重的时候，自然想到了散列表（哈希表），所以每次新建一个节点时，都将原链表里的节点和新的节点放入HashMap中，以原节点为键，新节点为值，这样在复制next指针指向的节点、或者是random指针指向的节点时，都可以在O(1)的时间内在散列表中找到已经复制过并放入新链表中的新节点。这个算法的时间复杂度是O(N)，额外空间复杂度是O(N)。
2. 使用散列表虽好，但是会占用O(N)的额外空间，如果可以使用常数级别的额外空间就最好了。方法一中占用空间的是新建的散列表HashMap，如果可以用别的方法将原节点与新节点联系起来，在O(1)的时间内可以找到对应的节点，就可以不使用散列表了。因为题目中已经告知随机指针只会指向链表中的节点或者是空节点，对于这一特性，每次在建立新节点时，将新节点插入到旧链表中相应的节点后面，如旧链表1→2->3→4，在遍历和插入之后就会变成1->1'->2->2'->3->3'->4->4'；而第二次遍历时将新节点里的random指针指向旧节点random指针指向的节点的next，如果在链表1->1'->2->2'->3->3'->4->4'中，节点4的random指针指向了节点1，那么就让节点4的next (4')的random指向节点1的next (1')；最后再遍历链表，将新的节点都取出来，组成新的链表。这个算法的时间复杂度是O(3N) = O(N)，额外空间复杂度是O(1)。
参考程序
关于Linkedin中如何复制随机指针就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：niceseo99@gmail.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
评论