链表代码书写技巧 | 极客时间《数据结构与算法之美-王争》链表(下)总结


很多面试官都喜欢让人现场手写代码,以考验一个人逻辑思维能力。因为链表代码中到处都是指针的操作、边界条件处理等,稍有不慎就容易产生Bug。所以链表代码写的好坏最可以看出一个人写代码是否足够细心,考虑问题是否全面,思维是否缜密。
极客时间课程《数据结构与算法之美》中,王争根据他的学习经历和工作经验,分享了六个写链表代码的技巧。

技巧一:理解指针或引用的含义

事实上,看懂链表的结构并不是很难,但是要把它和指针混在一起就很容易让人摸不着头脑。所以,要想写对链表代码,首先要理解好指针。
在C语言中,有指针的概念,而在JAVA、Python等语言中,取而代之的是“引用”的概念,不管是“引用”还是“指针”,本质上他们是一样的,都是用于存储所指对象的内存地址
关于指针的概念,用一句话来辅助理解一下:

  1. 将某个变量赋值给指针,实际上是将这个变量的地址赋值给了这个指针
  2. 或者可以反过来说,被赋值的指针中,存储了这个变量的内存地址,通过指针可以找到这个变量。

技巧二:警惕指针丢失或者内存泄漏

常见的指针丢失实例:
我们希望在一个单链表的结点a和结点b之间插入结点x,一定要先用结点x指向结点b,然后再用结点a指向结点x,如果修改指向的顺序写反了,就会造成指针丢失。
内存泄漏:是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放,造成系统内存的浪费,导致程序运行速度减慢甚至系统崩溃等严重后果。
在有些语言中,比如C语言,内存管理由程序员负责,如果没有手动释放结点对应的内存,就会造成内存泄漏。如果插入结点时指针丢失,或者删除结点时未手动释放内存空间,都会造成内存泄漏。

技巧三:利用哨兵简化实现难度

在链表的头部和尾部进行插入、删除等操作时,一般需要特殊处理,实现起来往往会比较繁琐,不简洁,而且也容易出错。引入不直接参与业务逻辑的“哨兵”结点,可以很好的解决边界问题。
哨兵结点,放置在链表的最前端,在任何时候,不管链表是否为空,head指针都会一直指向这个哨兵结点。我们把这种有哨兵结点的链表称为带头链表,相反,没有哨兵结点的链表称为不带头链表
带头链表示意图

技巧四:重点留意边界条件处理

软件开发中,代码在一些边界或者极端情况下最容易产生BUG。要实现没有BUG的链表代码,对于边界情况一定要重点考虑。
几个常见的边界特殊情况:

  1. 链表为空
  2. 链表只含一个结点
  3. 链表只含两个结点
  4. 头结点和尾结点

技巧五:举例画图,辅助思考

链表操作中的指针跳转,是一个挺复杂的事情,单靠脑袋思考,很容易被绕晕。所以可以用举例法画图法来辅助思考,避免脑容量不够。

技巧六:多写多练,没有捷径

以上只是总结出来的思维技巧,真正想把链表相关的问题做透,还是需要多做练习题,熟能生巧!
列举五个常见的链表操作:

  1. 单链表翻转
  2. 链表中环的检测
  3. 两个有序的链表合并
  4. 删除链表倒数第n个结点
  5. 求链表的中间结点

本文发表于2018年10月25日 19:36
阅读 1250 讨论 0 喜欢 0

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

6409 2086776
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

这个世界上,别人只会看你现在的样子而不是以后的样子。你以后的样子只有自己才相信。如果没有执行力,一切都是虚妄。

对普通人来说,人和人相处其实最重要的是感觉。感觉不好,你说什么都没用,怎么解释都没用,越说越错,反正最后不好的锅都往你身上扣。所谓“说你行你就行,不行也行。说你不行,你就不行,行也不行”就是这个意思。狼要吃人根本不需要理由,你也同样叫不醒装睡的人。遇到这种情况,早点闪人才是上策。不过大部分人的问题是没有闪人的心态,能力,和资源。

考985不牛逼,考上才牛逼。创业不牛逼,创业成功才牛逼。这个社会上很多人把目标当成牛逼的资本,牛逼哄哄的,死活不听劝,然后做的一塌糊涂,给别人添麻烦,让别人帮他料理后事,对此只能呵呵。

当你尝到用生气解决问题的甜头后,你就懒得再用其他方式了。你却忽略了,生气是鸩毒啊,剂量用够了,你的关系也玩完了。

年轻的时候你只搞事业不谈恋爱,等你事业有成了,钱相对自由了,你可能已经没有荷尔蒙了。

如果你经常雇佣比你矮小的人,将来我们就会变成矮人国,变成一家侏儒公司。相反,如果你每次都雇用比你高大的人,日后我们必能成为一家巨人公司。

如果一个人有充裕的时间去完成一项工作,那么他就会放慢节奏或者增加其他不必要的工作,直到花光所有的时间。

天空不是人类休息的地方,人类应该去亲近海洋。

一个人的正直程度,取决于他肯为原则付出的牺牲。

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.