专栏首页前沿技墅算法面试能过几关:咱也不知道,咱也不敢问

算法面试能过几关:咱也不知道,咱也不敢问

本文作者:魏梦舒

微信公众号“程序员小灰”的作者,具有多年软件行业从业经验,先后在京东金融、摩拜科技从事研发工作,对算法有一定的兴趣和经验。

题目

有一个单向链表,链表中有可能出现“环”,就像下图这样。那么,如何用程序来判断该链表是否为有环链表呢?

哦,让我想想啊……

有了!从头节点开始遍历整个单链表

方法1

首先从头节点开始,依次遍历单链表中的每一个节点。每遍历一个新节点,就从头检查新节点之前的所有节点,用新节点和此节点之前所有节点依次做比较。如果发现新节点和之前的某个节点相同,则说明该节点被遍历过两次,链表有环;如果之前的所有节点中不存在与新节点相同的节点,就继续遍历下一个新节点,继续重复刚才的操作。

就像图中这样,当遍历链表节点7时,从头访问节点5和节点3,发现已遍历的节点中并不存在节点7,则继续往下遍历。

当第2次遍历到节点2时,从头访问曾经遍历过的节点,发现已经遍历过节点2,说明链表有环。

假设链表的节点数量为n,则该解法的时间复杂度为O(n2)。由于并没有创建额外的存储空间,所以空间复杂度为O(1)。

这姑且算是一种方法,效率有没有可能更高?

哦,让我想想啊……

或者,我创建一个哈希表,然后……

方法2

首先创建一个以节点ID为Key的HashSet集合,用来存储曾经遍历过的节点。然后同样从头节点开始,依次遍历单链表中的每一个节点。每遍历一个新节点,都用新节点和HashSet集合中存储的节点进行比较,如果发现HashSet中存在与之相同的节点ID,则说明链表有环,如果HashSet中不存在与新节点相同的节点ID,就把这个新节点ID存入HashSet中,之后进入下一节点,继续重复刚才的操作。

遍历过5、3的效果图

遍历过5、3、7、2、6、8、1的效果图

当再一次遍历节点2时,查找HashSet,发现节点已存在。

由此可知,链表有环。

这个方法在流程上和方法1类似,本质的区别是使用了HashSet作为额外的缓存。

假设链表的节点数量为n,则该解法的时间复杂度是O(n)。由于使用了额外的存储空间,所以算法的空间复杂度同样是O(n)。OK,这种方法在时间上已经是最优了。

有没有可能在空间上也得到优化?

让空间复杂度降低?

……同时让时间复杂度不变,想不出来啊

没关系,今天就到这里,回家等通知吧。

方法3

小灰,刚刚的面试结果怎么样?

唉……

给我讲讲怎么更高效判断链表有环呀?

有环链表判断是基础,面试官都喜欢考查

有一个巧妙的方法——利用两个指针

首先创建两个指针p1和p2(在Java里就是两个对象引用),让它们同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针p1每次向后移动1个节点,让指针p2每次向后移动2个节点,然后比较两个指针指向的节点是否相同。如果相同,则可以判断出链表有环,如果不同,则继续下一次循环。

第1步,p1和p2都指向节点5。

第2步,p1指向节点3,p2指向节点7。

第3步,p1指向节点7,p2指向节点6。

第4步,p1指向节点2,p2指向节点1。

第5步,p1指向节点6,p2也指向节点6,p1和p2所指相同,说明链表有环。

学过小学奥数的读者,一定听说过数学上的追及问题。此方法就类似于一个追及问题。

在一个环形跑道上,两个运动员从同一地点起跑,一个运动员速度快,另一个运动员速度慢。当两人跑了一段时间后,速度快的运动员必然会再次追上并超过速度慢的运动员,原因很简单,因为跑道是环形的。

假设链表的节点数量为n,则该算法的时间复杂度为O(n)。除两个指针外,没有使用任何额外的存储空间,所以空间复杂度是O(1)。

明白了,这真是个好方法!

本文节选自电子工业出版社博文视点新书《漫画算法:小灰的算法之旅》。

本文分享自微信公众号 - 前沿技墅(Edge-Book),作者:崔志伟/编

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 复杂网络算法在平台业务安全中的应用

    对于电商平台和社交平台为主的平台业务,其安全涉及方方面面,常见的如刷单、黑灰产。本文以 Louvain、FRAUDAR 和 CatchSync 这三种典型的复杂...

    用户1682855
  • 卷积网络虽动人,胶囊网络更传“神”

    用户1682855
  • 持续交付:云原生应用的“十二要素”

    “独立系统的架构原则”(https://isa-principles.org/)与“十二要素应用”密切相关,但前者更注重架构方面。这些原则基于微服务,尤其是自包...

    用户1682855
  • 重温数据结构:理解 B 树、B+ 树特点及使用场景

    B 树就是常说的“B 减树(B- 树)”,又名平衡多路(即不止两个子树)查找树,它和平衡二叉树的不同有这么几点:

    张拭心 shixinzhang
  • js插入节点appendChild和insertBefore

    首先 从定义来理解 这两个方法:  appendChild() 方法:可向节点的子节点列表的末尾添加新的子节点。语法:appendChild(newchild)...

    蓓蕾心晴
  • 数据结构之二叉树解析

    可是,排序有快速排序,归并排序,查找有二分法,甚至直接遍历查找,我干啥要使用二叉树呢?

    Kevin_Zhang
  • GR运维手册 - 第一册 苦海岸边,GR的基础知识

    作者简介: ? 刘伟 云和恩墨开源解决方案事业部首席架构师 多年一线互联网企业DBA经历,对MySQL、NoSQL,PostgreSQL等各类开源数据库均有涉猎...

    数据和云
  • 一文搞定 Redis 复制(全会的举个手看看)

    Step 2:从节点只是保存了 slaveof 命令中主节点的信息,并没有立即发起复制。

    良月柒
  • 红黑树(二):删除操作

    构造上,节点会有三种可能:其一是删除节点的孩子都为Nil,其二是删除节点的一个孩子节点为Nil,其三是删除节点的两个孩子节点都不为Nil。而如果两个节点都不为N...

    每天学Java
  • 二叉树搜索树(程序员都知道)

    程序你好

扫码关注云+社区

领取腾讯云代金券