数据结构与算法之美

学习内容 :链表(下):如何轻松写出正确的链表代码?

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

无论是指针还是引用,他们的意思都是一样的:存储所指对象的内存地址。

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

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

img

如图所示,我们希望在结点 a 和相邻的结点 b 之间插入结点 x,假设当前指针 p 指向结点 a。

我们插入结点时,一定要注意操作的顺序,要先将结点 x 的 next 指针指向结点 b,再把结点 a 的 next 指针指向结点 x,这样才不会丢失指针,导致内存泄漏。

删除链表结点时,也一定要记得手动释放内存空间

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

针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。

哨兵,解决的是国家之间的边界问题。同理,这里说的哨兵也是解决“边界问题”的,不直接参与业务逻辑。

head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反,没有哨兵结点的链表就叫作不带头链表。

img

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

我经常用来检查链表代码是否正确的边界条件有这样几个:

  • 如果链表为空时,代码是否能正常工作?
  • 如果链表只包含一个结点时,代码是否能正常工作?
  • 如果链表只包含两个结点时,代码是否能正常工作?
  • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?

代码的运行的边界情况/异常情况

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

举例法和画图法。

你可以找一个具体的例子,把它画在纸上,释放一些脑容量,留更多的给逻辑思考,这样就会感觉到思路清晰很多。

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

img

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

常见的链表操作:

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第 n 个结点
  • 求链表的中间结点