前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BAT算法面试题(12)--环形链表(哈希表法)

BAT算法面试题(12)--环形链表(哈希表法)

作者头像
CC老师
发布2019-01-23 15:03:10
4440
发布2019-01-23 15:03:10
举报
文章被收录于专栏:HelloCode开发者学习平台

小编温馨提示,今天是我们坚持学习算法的第12天!

你已经比80%的开发者优秀了很多了哦.加油继续! just do it

一.面试题目

给定一个链表,判断链表中是否有环. 难度升级: 试试能否在不使用额外空间解决此问题?

二.解决方案(哈希表)

思路

我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表.常用方法,一般是使用哈希表.

算法

我们遍历所有的节点并在哈希表中存储每个结点的引用(或内存地址).如果当前节点为空结点null,表示我们已经检测到链表的末尾的下一个节点.那么表示我们已经完成了链表的遍历,并且此链表不是环形链表.如果当前结点的引用已经存在过哈希表中,那么即可立马返回true(表示此链表为环形链表).

三.代码

Java Code

四.复杂度分析

  • 时间复杂度: O(n),对于含有n个元素的链表,我们访问每个元素最多一次.添加一个结点到哈希表中只需要花费O(1)的时间.
  • 空间复杂度:O(n),空间取决于添加哈希表中的元素数目.最多可以添加n个元素.

五.学习建议

  • 只要明白哈希表,即可解决这个问题.!

小编OS:

成为一名算法工程师的前提是什么?是在算法上坚持不懈.

突破开发者的瓶颈前提是什么?永不止步的学习!

成为一名优秀的开发者前提是什么? 不断学习算法!

成为一名优秀的人前提是什么? 你身边围绕更多优秀的人!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-08-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 HelloCode开发者学习平台 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 小编温馨提示,今天是我们坚持学习算法的第12天!
  • 一.面试题目
  • 二.解决方案(哈希表)
    • 思路
      • 算法
      • 三.代码
      • 四.复杂度分析
      • 五.学习建议
      • 小编OS:
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档