阅读 174

Linkedin 面试题 | 复制随机指针

专栏 | 九章算法
网址 | www.jiuzhang.com

题目描述

给出一个链表,每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。

算法分析

深度拷贝一个普通链表的算法非常简单,因为每一个节点只有一个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)。

参考程序

面试官角度分析

这道题目能够分析清楚两个不同思路的时间复杂度和空间复杂度就能够拿到hire。

LintCode相关练习题
www.lintcode.com/en/problem/…


推荐阅读:



欢迎关注我的微信公众号:九章算法(ninechapter)。
精英程序员交流社区,定期发布面试题、面试技巧、求职信息等

九章算法,IT教育领域的深耕者
九章算法,IT教育领域的深耕者

关注下面的标签,发现更多相似文章
评论