重新认识链表（下）

写链表代码是最考验 逻辑思维能力 的，指针来回指，指着指着就指迷糊，在写代码之前先注意这么几个问题。

问题1：什么是指针？

定义：

有些语言有“指针”的概念，比如 C 语言；有些语言没有指针，取而代之的是“引用”，比如 Java 、Python。不管是“指针”还是“引用”，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

举例：

最常见的指针代码应该是这个了， p->next=q 。它的意思是说p 结点中的 next 指针存储了 q 结点的内存地址。

问题2：什么是指针丢失和内存泄漏？

在插入结点时，一定要注意操作的顺序。

因为操作不当的时候，很容易造成指针丢失。比如a ->b之间插入一个c，同时不注意的时候很容易这么写

//声明一个p;

p->next = c; // 将 p 的 next 指针指向 c 结点; 

c->next = p->next; // 将 c 的结点的 next 指针指向 b 结点;

这就很容易让链表断成两半，造成指针丢失。正确的写法是将二三两行代码顺序换过来即可。

删除链表结点时，也一定要记得手动释放内存空间。

和插入一样，如果不及时释放内存空间，积少成多，很容易造成内存泄漏。

技巧：利用哨兵节点简化实现难度

哨兵节点主要是处理边界问题的，并不直接参与业务逻辑，当引入哨兵节点的时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫 带头链表 。相反，没有哨兵结点的链表就叫作 不带头链表 。

练习：

以单链表为例，所有源码均已上传至github: github.com/chaoaiqi/st…

声明一个单链表类

1.实现单链表、循环链表、双向链表，支持增删操作

顺序插入

删除，难点就一行q.next = q.next.next;

查询，分两个，一个是根据下标查询，一个是根据value查询

测试结果：

2.单链表反转

该实现的思想是： 从前往后反转各个结点的指针域的指向 。

将当前节点cur的next节点 缓存到nextNode，然后更改当前节点指针指向上一结点prevNode。也就是说在反转当前结点指针指向前，先把当前结点的指针域用nextNode临时保存，以便下一次使用

.

测试结果：

3.链表中环的检测

该检测的核心思想是： 快慢指针法 。在这里，满指针每走一步，快指针走两步，可以用 数学归纳法 来考虑，首先，如果链表是个环，所以相遇的过程可以看作是快指针从后边追赶慢指针的过程。那么

测试结果:

4.求链表的中间结点

该实现也是用到了 快慢指针法 。

代码如下：

测试结果如下：

5.删除链表倒数第 n 个结点

该实现依旧用到了快慢指针法，不过和之前的有一点区别。以node长度为n，删倒数第k（k<n）个为例。首先，第一个while先计算如果正着删，需要让慢指针走几步，计算为n-k。第二个while循环则通过遍历快指针计算定位需要走n-k步,得到preNode。然后判断是否为空，不为空则常规方法删除。

测试结果

还有种思路是通过递归来进行删除，本次不做阐述。

6.两个有序的链表合并

该实现的思路是，首先比较两个有序链表，如果pNode为空，直接返回qNode，反之qNode为空，则返回pNode，然后比较p和q，将最小的节点赋值给resNode，同时将最小的节点向后移动一位。设置一个node指向resNode节点，用于方便连接其它节点，在继续比较p和q，同样选出小的那个节点，将该节点设为合并后的链表的第二个节点，用node.next表示该节点，一直重复上述过程，直到p和q有一个为null，然后再将不为null的节点放入新链表后即可。

测试结果：