链表代码注意事项

2018-10-08 本文已影响0人 _Rice_

1、理解指针或引用的含义

比如C语言是指针，就是相当于JAVA的引用

C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。

Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑。

哨兵结点其实就是链表的头结点，不存在数据，有next变量。

哨兵结点在很多地方都会用到，比如插入排序、归并排序、动态规划等待

image.png

边界问题没有充分考虑好容易产生BUG。

在编写的时候一定要检查边界问题是否考虑全面、以及代码在边界条件下能否正常运行

例如，但不限于：

思想：指针方向取反

思想：分别处理两个链表都有结点、只有一个链表有结点的情况

思想：找到第n-1个结点，期next指向第n+1个结点

思想：利用快慢指针法

设置两个指针slow和fast，两个指针同时向前走，fast指针每次走两步，slow指针每次走一步，注意区分长度是奇偶性。