不得不知道的实用数据结构算法（二）

依旧是简单总结，主要还是一个思路上的应对问题，不去探讨实现细节，有机会单独讨论实现细节（毕竟我忘得差不多了）。

首先先回忆链表的定义，以及其基本操作：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

我们经常会去比较顺序表与链表的优劣，令我们印象最深刻的往往是插入算法的比较，下面列个表格比较一下基本操作的时间复杂度：

相对顺序表而言，链表的操作貌似更快，但是也更有挑战性，因为没有了随机存取的特性，导致链表在获取元素时是很麻烦的，但是，往往这种拧巴的东西就很喜欢出题。

这个方法与其说叫做一种技巧，不如说是一种实现的思路。我们考虑单向带头结点的有序链表，下面开始分类说明：

储存：当我们需要在某个元素前插入一个新的节点，那么我在找到该节点时还需要这个节点的前一个节点，这时候我们就需要一个双指针。不要小看这个思路，储存好数据能做很多事情（但是我不太会举例子）

不同链表：比如合并两个有序链表，我们也需要使用多个指针

二分查找、快速排序：这是从排序和查找中拿来的思路，一般都是比较容易看出的，但是用在链表上并不都快，二分查找只有在随机存取下才快；快排的分治的思路是在链表上很常应用的

对撞指针：就是首尾指针，双向遍历，但是要注意这里要求就必须是双向链表了

这个就比较链表了，解决的问题主要有：

有公共节点的链表：

有环的链表：

分块位置关系的链表

这个实际上就是头插法的灵活使用，其解决的问题与前面提过的顺序表是一致的。