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

指针或引用存储的是对象的内存地址。将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针。

p->next=q 表示 p 结点中的 next 指针存储了 q 结点的内存地址。从左到右读就可以,p 的下一个结点就是 q。

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

拿单链表的插入举例。在结点 a 和相邻的结点 b 之间插入 x,假设当前指针 p 指向结点 a。

插入结点

p->next = x;  // 将 p 的 next 指针指向 x 结点;
x-next = p -> next;  // 将 x 的结点的 next 指针指向 b 结点;

很显然,上面的代码执行结果有问题。结点 x 最终指向自己,这样链表就断开了,造成内存泄漏。所以应该颠倒一下顺序。

在插入结点时,一定要注意操作的顺序,这样才不会丢失指针。删除结点时,一定记得手动释放内存,以免产生内存泄漏。

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

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

引入哨兵结点,不管链表是不是空,head 指针都会一直指向这个哨兵结点。把这种有哨兵结点的链表叫带头链表。相反。没有哨兵结点的链表就叫作不带头链表。

哨兵结点是不存储数据的。因为哨兵结点一直存在,所以插入第一个结点和插入其他结点,删除最后一个结点和删除其他结点,都可以使用相同的代码实现逻辑了。

带头链表

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

常用来检查链表代码是否正确的边界条件:

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

实际上,不光是写链表代码,在写任何代码时,也千万不要只实现业务正常情况下的功能,一定要多想想,代码在运行的时候,可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对,这样写出来的代码才够健壮!

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

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

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

精选了 5 个常见的链表操作,作为练习的题目。

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