链表：如何轻松写出正确的链表代码？
几个写链表代码的技巧
1.理解指针或引用的含义 以c语言中的指针为例(java，python中取代之的是引用，都是存储所指对象的内存地址)，理解指针的含义： 将某个变量赋值给指针，实际上就是将这个变量的内存地址赋值给指针，也就是说，指针中存储了这个变量的内存地址，指向这个变量，通过指针就能找到这个变量。 2.警惕指针丢失和内存泄露 指针丢失分析：（以单链表的插入操作为例）
我们要在a节点和b节点中插入节点x,假设p指针指向a 如果将代码写成如下，就会发送指针丢失： a.next = x x.next = a.next 插入节点时要注意操作顺序，以上问题，只需要颠倒一下两行代码的顺序即可 删除节点要注意手动释放内存(类似java这样的语言就不需要了) 3.利用哨兵简化实现难度（单链表为例） 对于插入操作，在两个节点中插入节点的操作如下： x.next = a.next a.next = x 但是如果要在链表头部插入节点，则上面代码不适用，需要进行特殊操作 x.next = head head = x 如果是插入空链表 head = x 对于删除操作，删除a,b节点中的节点x a.next = a.next.next 对于删除最后一个节点 a.next = null 对于删除第一个节点 head = head.next 针对链表的插入和删除操作，对于首节点和尾节点都需要进行特殊处理 为了解决上面的问题我们可以引入哨兵节点 我们称有哨兵节点的链表叫做带头链表，无哨兵节点的链表叫做不带头链表
举例说明，使用带头链表带来的性能提升： 代码一： // 在数组 a 中，查找 key，返回 key 所在的位置 // 其中，n 表示数组 a 的长度 int find(char* a, int n, char key) { // 边界条件处理，如果 a 为空，或者 n<=0，说明数组中没有数据，就不用 while 循环比较了 if(a == null || n <= 0) { return -1; } int i = 0; // 这里有两个比较操作：i<n 和 a[i]==key. while (i < n) { if (a[i] == key) { return i; } ++i; } return -1; } 代码2： // 在数组 a 中，查找 key，返回 key 所在的位置 // 其中，n 表示数组 a 的长度 // 我举 2 个例子，你可以拿例子走一下代码 // a = {4, 2, 3, 5, 9, 6} n=6 key = 7 // a = {4, 2, 3, 5, 9, 6} n=6 key = 6 int find(char* a, int n, char key) { if(a == null || n <= 0) { return -1; } // 这里因为要将 a[n-1] 的值替换成 key，所以要特殊处理这个值 if (a[n-1] == key) { return n-1; } // 把 a[n-1] 的值临时保存在变量 tmp 中，以便之后恢复。tmp=6。 // 之所以这样做的目的是：希望 find() 代码不要改变 a 数组中的内容 char tmp = a[n-1]; // 把 key 的值放到 a[n-1] 中，此时 a = {4, 2, 3, 5, 9, 7} a[n-1] = key; int i = 0; // while 循环比起代码一，少了 i<n 这个比较操作 while (a[i] != key) { ++i; } // 恢复 a[n-1] 原来的值, 此时 a= {4, 2, 3, 5, 9, 6} a[n-1] = tmp; if (i == n-1) { // 如果 i == n-1 说明，在 0...n-2 之间都没有 key，所以返回 -1 return -1; } else { // 否则，返回 i，就是等于 key 值的元素的下标 return i; } } 4.重点留意边界条件处理 我经常用来检查链表代码是否正确的边界条件有这样几个： 如果链表为空时，代码是否能正常工作？ 如果链表只包含一个结点时，代码是否能正常工作？ 如果链表只包含两个结点时，代码是否能正常工作？ 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？ 除了上面四点，还可能需要根据具体场景思考一下
5.距离画图，辅助思考
6.多多练习 至少要能熟练手写以下代码 单链表反转 链表中环的检测 两个有序链表合并 删除链表倒数第n个节点 求链表的中间节点 练习题LeetCode对应编号：206，141，21，19，876 
更多精彩
