1、理解指针或引用的含义
比如C语言是指针，就是相当于JAVA的引用
2、警惕指针丢失和内存泄漏
C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。
Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑。
3、哨兵简化实现难度
哨兵结点其实就是链表的头结点，不存在数据，有next变量。
哨兵结点在很多地方都会用到，比如插入排序、归并排序、动态规划等待
- 有哨兵结点的链表叫带头链表，没有哨兵结点的链表叫不带头链表
image.png
重点留意边界问题处理
边界问题没有充分考虑好容易产生BUG。
在编写的时候一定要检查边界问题是否考虑全面、以及代码在边界条件下能否正常运行
例如，但不限于：
- 链表为空时
- 链表只包含一个结点
- 链表只包含两个结点
- 头结点和尾结点的处理
4、举例画图，辅助思考
5、多写多练，熟能生巧，没有捷径
应用
算法实现考虑递归和非递归实现
- 单链表反转
思想：指针方向取反
- 两个有序的链表合并
思想：分别处理两个链表都有结点、只有一个链表有结点的情况
推荐阅读：两个有序的链表合并
- 删除链表倒数第n个结点
思想：找到第n-1个结点，期next指向第n+1个结点
- 求链表的中间结点
思想：利用快慢指针法
设置两个指针slow和fast，两个指针同时向前走，fast指针每次走两步，slow指针每次走一步，注意区分长度是奇偶性。
推荐阅读：实现寻找链表的中间节点
网友评论