【编程起跑线】05 链表

链表，作为在内存中非连续分配的数据结构，因为其灵活性往往容易出错，这里我们会通过深入理解来教大家一些解决链表问题的基本方法。

更新历史

2019.08.05：编入新系列
2016.01.22：完成初稿

链表

链表是非常基础和常用的一个数据结构，尤其是在解析器(parser)、游戏和搜索算法中。而且很多时候会用来实现下面的 ADT(Abstract Data Type)：

堆栈 Stack
集合 Set
哈希表 Hash Table

我们来重温一下实现某个数据结构要做的五个事情：

抽象理解
写出
Write Applications
Select, Design, Implement
Analyze the Implementation

需要掌握的链表操作：

插入
删除
检查是否有环
保证程序的健壮性（主要是头为空的时候）

其他比较特别的操作：

合并 N 个链表
反转链表
截取链表的一部分
寻找链表的 1/N

解题策略

链表(linked list)是一种常见的线性数据结构。对于单向链表(singly linked list)，每个节点有一个 next 指针指向后一个节点，还有一个成员变量用以存储数值；对于双向链表(doubly Linked List)，还有一个 prev 指针指向前一个节点。与数组类似，搜索链表需要O(n)的时间复杂度，但是链表不能通过常数时间 O(1) 读取第k个数据。链表的优势在于能够以较高的效率在任意位置插入或删除一个节点。

当涉及对头节点的操作，我们不妨考虑创建哑节点
由于题目涉及在链表中寻找特定位置，我们用两个指针变量以不同的速度遍历该链表
实现链表的逆转时，循环遍历链表, 每次只处理当前指针的 next 变量

基本解题策略

当涉及对头节点的操作，我们不妨考虑创建哑节点
题目涉及在链表中寻找特定位置，我们用两个指针变量以不同的速度遍历该链表
循环遍历链表, 每次只处理当前指针的next 变量，由此实现链表的逆转
凡是修改单向链表的操作，只需考虑：
- 哪个节点的next指针会受到影响，则需要修正该指针；
- 如果待删除节点是动态开辟的内存空间，则需要释放这部分空间(C/C++)

基本操作

检验有效性
- 访问某个节点 curt.next 时，要检验 curt 是否为 null
反转链表
- 要把反转后的最后一个节点（即第一个节点）指向 null
删除某个节点
- 由于需要知道前继节点的信息，而前继节点可能会导致表头产生变化，所以需要一些技巧 Dummy Node
- 全部操作结束后，判断是否有环；若有，则置其中一端为 null

快慢指针

快速找出未知长度单链表的中间节点
- 设置两个指针 *fast 和 *slow 都指向头节点
- *fast 移动速度是 *slow 的两倍
- *fast 指向末尾节点时，*slow 正好就在中间
判断单链表是否有环
- 设置两个指针 *fast 和 *slow 都指向头节点
- *fast 移动速度是 *slow 的两倍
- 如果 *fast == null 说明该单链表不是循环链表
- 如果 *fast == *slow 说明该链表是循环链表
找倒数第 N 个节点
- 设置两个指针 fast 和 slow 都指向头节点
- *fast 先移动 N 步，然后两个指针一起前进
- *fast 到达末尾时，*slow 即为倒数第 N 个节点

链表的基本操作

凡是修改单向链表的操作，只需考虑：

哪个节点的next指针会受到影响，则需要修正该指针；
如果待删除节点是动态开辟的内存空间，则需要释放这部分空间(C/C++)

毕竟，一个链表节点，无非是包含value和next这两个成员变量的数据结构而已。对于双向链表，类似的，则只需额外考虑谁的prev指针会受到影响。

举例如下：

void delNode(ListNode *prev) {
  ListNode *curr = prev->next;
  // 删除curr节点只会使prev节点的next受到影响
  prev->next = curr->next;
  delete curr; // 清理trash指针
}

注：操作链表时务必注意边界条件：curr == head, curr == tail 或者 curr == NULL

两种存储方式
- 顺序存储结构：随机读取，访问时是 O(1)
- 链式存储结构：插入和删除 O(1)，访问时最坏是 O(n)
分类（根据指针域）
- 单向链表
- 双向链表
- 循环链表

反转链表

访问某个节点 curt.next 时，要检验 curt 是否为 null
要把反转后的最后一个节点（即第一个节点）指向 null

删除某个节点

由于需要知道前继节点的信息，而前继节点可能会导致表头产生变化，所以需要一些技巧 Dummy Node
链表指针的鲁棒性
- 访问某个节点 curt.next 时，要检验 curt 是否为 null
- 全部操作结束后，判断是否有环；若有，则置其中一端为 null

Dummy Node

是一个虚拟节点 dummy.next = head
针对单向链表没有前向指针的问题，保证链表的 head 不会在删除操作中丢失
也可以用来进行 head 节点（但比较少见）
当链表的 head 可能有变化时，使用 dummy node 可以简化代码，最后返回 dummy.next 即可

快慢指针

快慢指的是指针向前移动的步长，一般来说，快指针每次移动 2，慢指针每次移动 1
主要有两个应用
- 快速找出未知长度单链表的中间节点
  - 设置两个指针 *fast 和 *slow 都指向头节点
  - *fast 移动速度是 *slow 的两倍
  - *fast 指向末尾节点时，*slow 正好就在中间
- 判断单链表是否有环
  - 设置两个指针 *fast 和 *slow 都指向头节点
  - *fast 移动速度是 *slow 的两倍
  - 如果 *fast == null 说明该单链表不是循环链表
  - 如果 *fast == *slow 说明该链表是循环链表
其他应用
- 找倒数第 N 个节点
  - 设置两个指针 *fast 和 *slow 都指向头节点
  - *fast 先移动 N 步，然后两个指针一起前进
  - *fast 到达末尾时，*slow 即为倒数第 N 个节点

2019 小土刀再启程