数据结构复习笔记 - 链表（下）

链表（下）：如何轻松写出正确的链表代码？

1. 技巧一：理解指针或引用的含义
   • 将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
2. 技巧二：警惕指针丢失和内存泄漏
   • 插入结点时，一定要注意操作的顺序
   • 删除链表结点时，也一定要记得手动释放内存空间
3. 技巧三：利用哨兵简化实现难度
   • 针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。
   • 也称为带头链表，去除对特除区域的单独处理，统一为相同的代码实现逻辑。
4. 技巧四：重点留意边界条件处理
   • 如果链表为空时，代码是否能正常工作？
   • 如果链表只包含一个结点时，代码是否能正常工作？
   • 如果链表只包含两个结点时，代码是否能正常工作？
   • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
5. 技巧五：举例画图，辅助思考
6. 技巧六：多写多练，没有捷径
   • 单链表反转
   • 链表中环的检测
   • 两个有序的链表合并
   • 删除链表倒数第 n 个结点
   • 求链表的中间结点

部分实现