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

有些语言有“指针”的概念,比如 C 语言;有些语言没有指针,取而代之的是“引用”,比如 Java、Python。不管是“指针”还是“引用”,实际上,它们的意思都是一样的,都是存储所指对象的内存地址。

什么是指针

将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量。

第二:警惕指针丢失和内存泄漏

对于有些语言来说,比如 C 语言,内存管理是由程序员负责的,如果没有手动释放结点对应的内存空间,就会产生内存泄露。所以,我们插入结点时,一定要注意操作的顺序,要先将结点 x 的 next 指针指向结点 b,再把结点 a 的 next 指针指向结点 x,这样才不会丢失指针,导致内存泄漏。所以,对于刚刚的插入代码,我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。

同理,删除链表结点时,也一定要记得手动释放内存空间,否则,也会出现内存泄漏的问题。当然,对于像 Java 这种虚拟机自动管理内存的编程语言来说,就不需要考虑这么多了。

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

哨兵作用?

哨兵作用是减少特殊情况的判断,比如判断是否是空链表,比如判越界,比如减少链表插入删除中对空链表的判断,比如例子中对i越界的判断。

哨兵用途:

利用哨兵简化编程难度的技巧,在很多代码实现中都有用到,比如插入排序、归并排序、动态规划等。

为什么用哨兵:

空链表与越界属于小概率情况,每一次操作代码都需要判断一次,而这一步在大部分情况下都会是多余的。而是用哨兵的巧妙就是提前将这种情况去除,比如给一个哨兵结点,以及将key赋值给数组末元素,让数组遍历不用判断越界也可以因为相等停下来。

使用哨兵的指导思想应该是将小概率需要的判断先提前扼杀,比如提前给他一个值让他不为null,或者提前预设值,或者多态的时候提前给个空实现,然后在每一次操作中不必再判断以增加效率。

哨兵相关知识:

https://www.zhihu.com/question/27155932

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

  1. 如果链表为空时,代码是否能正常工作?

  2. 如果链表只包含一个结点时,代码是否能正常工作?

  3. 如果链表只包含两个结点时,代码是否能正常工作?

  4. 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?

第五:举例法和画图法,辅助思考

单链表中插入一个数据这样一个操作,我一般都是把各种情况都举一个例子,画出插入前和插入后的链表变化,如图所示:

download.jpg

第六:多写多练,没有捷径

5个常见的链表操作

  1. 单链表反转

  2. 链表中环的检测

  3. 两个有序的链表合并

  4. 删除链表倒数第 n 个结点

  5. 求链表的中间结点

内容小结

写链表代码是最考验逻辑思维能力的。因为,链表代码到处都是指针的操作、边界条件的处理,稍有不慎就容易产生 Bug。链表代码写得好坏,可以看出一个人写代码是否够细心,考虑问题是否全面,思维是否缜密。所以,这也是很多面试官喜欢让人手写链表代码的原因。

LeetCode练习题

对应编号:206,141,21,19,876

参考网址:

https://time.geekbang.org/column/article/41149

本文地址: http://chenxm.cc/article/963.html
版权声明: 本文为原创文章,版权归  陈新明  所有,欢迎分享本文,转载请保留出处!
上一篇: 如何实现LRU缓存淘汰算法?
下一篇: python2安装gunicorn提示ERROR: Package 'gunicorn' requires a different Python: 2.7.12 not in '>=3.4'
发表评论

还没有留言,还不快点抢沙发?