学习自极客时间的《数据结构与算法之美》 作者：王争
链表
一. 链表和数组的区别
数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。
而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。其中，我们把内存块称为链表的“结点”。
二. 链表的插入和删除
- 在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。
- 而在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的。
三. 链表的分类
链表有很多种,如常见的单链表,双向链表和循环链表等。
** 1. 单链表**
为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。我们把这个记录下个结点地址的指针叫作后继指针 next。
我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
** 2. 循环链表**
单链表的尾指针是指向空地址的,而循环链表的尾指针是指向头指针的。
循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。
** 3. 双向链表**
单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
双向链表的高效体现在哪里
删除操作
在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：
- 删除结点中“值等于某个给定值”的结点；
- 删除给定指针指向的结点。
对于单链表来说:
- 第一种情况,虽然删除的时间复杂度为O(1), 但是我们需要遍历节点并一一和给定的值对比,直到找到值等于给定值的结点,所以删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。
- 对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。
插入操作也是类似的。除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
问题思考
如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？
力扣第234题 : https://leetcode-cn.com/problems/palindrome-linked-list/submissions/
使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步。在慢指针前进的过程中，同时修改其 next 指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等。
https://github.com/wangzheng0822/algo/blob/master/python/06_linkedlist/palindrome.py
关于链表的题目
单链表反转
力扣第206题:https://leetcode-cn.com/problems/reverse-linked-list/链表中环的检测
力扣第141题:https://leetcode-cn.com/problems/linked-list-cycle/两个有序的链表合并
力扣第21题:https://leetcode-cn.com/problems/merge-two-sorted-lists/k个有序的链表合并
力扣第23题:https://leetcode-cn.com/problems/merge-k-sorted-lists/删除链表倒数第 n 个结点
力扣第19题:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/求链表的中间结点
力扣第876题:https://leetcode-cn.com/problems/middle-of-the-linked-list/两两交换链表中的节点
力扣第24题:https://leetcode-cn.com/problems/swap-nodes-in-pairs/
我做完这几道题后,总结了一个道理,链表经常使用快慢指针来解决问题。