2.3 链表（二）

怎么写好链表代码

1. 理解指针或引用的含义
   指针存储了指定变量的内存地址，通过指针就能找到这个变量
   p -> next = q代表p节点的next指针中存储了q节点的内存地址
   常用的还有p->next=p->next->next 直接把p的next指针指向p节点的下下一个加点的内存

2. 警惕指针丢失和内存泄露
   插入节点时一定要注意操作顺序，在a、b节点中插入c节点时，必须先把c的next指向b，再把a的next指向c。
   同时删除链表节点时也记得手动释放内存空间。

3. 利用哨兵简化实现难度
   无论插入链表的第一个节点还是删除链表的最后一个节点，我们都需要特殊处理，为了避免和简化操作，引入了哨兵概念。它不参与业务逻辑，只解决边界问题。
   如果链表中存在哨兵节点，它会被称作带头链表，相反，没有哨兵节点的链表被叫做不带头链表。
   

   image.png

4. 重点留意边界

   • 如果链表为空，代码是否正常？
   • 如果链表只有一个节点，代码是否正常？
   • 如果链表只有两个节点时，代码是否正常？
   • 代码处理头结点和尾结点时，是否正常？

5. 举例画图，辅助思考
   在写的同时在草稿上列出具体内容或者画出相关的节点增减，这能有效帮助构筑具体的操作步骤

6. 多写多练，没有捷径
   多写，熟练以下内容

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

此文章为2月Day4学习笔记，内容来源与极客时间《数据结构与算法之美》