技巧1：理解指针或引用的含义
将某个遍历赋值给指针，实际上就是将这个变量地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
类似 p->next=q p结点中的next指针存储了q结点的内存地址，也可以说p的next指向q。
p->next=p->next->next p结点的next指针存储了p结点的下下一个结点的内存地址。
技巧2：警惕指针丢失和内存泄漏
指针怎么丢的呢？
看单链表的插入操作：
假设当前指针p指向a 如果代码如下，就会发生指针丢失和内存泄漏问题p->next = x; // 将p的next指针指向x结点；x->next = p->next; // 将x的结点的next指针指向b结点；
此时x指向了自己，链表断成两半，b后面结点无法访问。
对于需要程序员负责的内存管理，如果没有释放结点对应的内存空间，就会发生内存泄漏。
所以，插入结点，一定注意操作顺序，一般对于该图中的三角形，一半从右到左进行。
所以上述代码，最好将两行颠倒一下。
删除节点一定记得手动释放内存空间。但Java这种虚拟机自动管理内存的编程语言，就不需要考虑那么多。
技巧3：利用哨兵简化实现难度
- 什么是“哨兵”？
链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。
- 未引入“哨兵”的情况
如果在p节点后插入一个节点，只需2行代码即可搞定：new_node—>next = p—>next;p—>next = new_node;
但，若向空链表中插入一个节点，则代码如下：if(head == null){head = new_node;}
如果要删除节点p的后继节点，只需1行代码即可搞定：p—>next = p—>next—>next;
但，若是删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：if(head—>next == null){head = null;}
从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。
3.引入“哨兵”的情况
“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。
哨兵就是减少了特殊情况的判断 ，原来需要考虑头或尾 有哨兵后，头尾和普通一致，不再需要。
空与越界可以认为是小概率情况，所以代码每一次操作都走一遍判断，在大部分情况下都会是多余的。
哨兵的巧妙就是提前将这种情况去除，比如给一个哨兵结点，以及将key赋值给数组末元素，让数组遍历不用判断越界也可以因为相等停下来。
使用哨兵的指导思想应该是将小概率需要的判断先提前扼杀，比如提前给他一个值让他不为null，或者提前预设值，或者多态的时候提前给个空实现，然后在每一次操作中不必再判断以增加效率。
技巧4：重点留意边界条件处理
经常用来检查链表是否正确的边界4个边界条件：
1.如果链表为空时，代码是否能正常工作？
2.如果链表只包含一个节点时，代码是否能正常工作？
3.如果链表只包含两个节点时，代码是否能正常工作？
4.代码逻辑在处理头尾节点时是否能正常工作？
正常写任何代码，再可能遇到哪些边界情况或者异常情况，都应该细细考虑。
技巧5：举例画图，辅助思考
核心思想：释放脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。
技巧6：多写多练
5个常见链表操作
1.单链表反转
2.链表中环的检测
3.两个有序链表合并
4.删除链表倒数第n个节点
5.求链表的中间节点
内容小结
正确链表代码的六个技巧。
练习题leetcode：206，141，21，19，876
若有收获，就点个赞吧
0 人点赞
