头疼链表？搞懂这18个斯坦福大学整理的和链表相关的问题，就再也不怕了

链表属于极其经典的数据结构之一，大家在学习数据结构的时候，一定学习过链表这种数据结构。虽然在实际生产环境中手写链表的场景并不多，但是链表依然是非常有用的一种数据结构，在很多语言的底层有着不可替代的作用。

最最重要的是，链表是笔试面试或者各种计算机水平考察中的常客。为什么？

首先，因为链表拥有着极其简单的结构，但却能引申出相当复杂优美的算法思想。这是因为同二叉树一样，链表也拥有着天然的递归性质！每一个链表节点的next，链接的是一个更小的链表！这使得近乎所有对链表的操作，都可以使用递归的方式完成。只不过由于链表天然是线性的，非常方便迭代遍历，使得很多人忽视了链表的递归性质。我个人认为，同二叉树一样，对于所有的链表的问题，在学习阶段，都有必要使用递归和非递归两种方式完成。这个过程将大大加深对递归的理解。很多同学会问我很多和二叉树相关的递归问题，但这些问题其实在链表中也是同样成立的。究其根本，是从链表的学习开始，就对递归没有建立深刻的认识。

另一方面，操作链表将不可避免的操作指针（C++中的指针，其他语言中的引用）。对指针或者引用这个概念的熟练掌握，是使用任何编程语言都逃不过的概念。而链表本身，提供了一个结构简单，却又能充分理解实验这个概念的最佳场所。

怎么学习链表？大多数数据结构教材都会对链表进行充分的讲解，并且辅以相关的练习题。但是很多教材中和链表相关的练习稍显混乱，显得不成体系。斯坦福大学的计算机系整理了一份和链表相关的18个问题，充分编程实践这18个问题，基本就可以说把“链表”这个知识点打通关了。我个人建议，对于还处于基础学习阶段的同学，对下列问题中的大多数问题，都可以思考使用递归和非递归两种方式完成。

这18个问题如下：

1. Count 计算链表的节点个数；

2. GetNth 获得链表第n个节点的值；

3. CreateList 根据数组（或者标准输入）创建链表；

   DeleteList 释放一个链表的所有节点空间（C++）；

4. Push 向链表头插入一个新节点；

   Pop 删除链表的第一个节点并返回；

   注意：我们可以将链表看做是一个队列，此时，向链表的头或者尾插入或者删除元素，就可以衍生出两个Push实现和两个Pop实现。大家也可以显示地将这四个方法命名为addFirst, addLast, removeFirst, removeLast（参考Java中的命名方式），并据此封装底层基于链表的栈，队列，双向队列等等线性数据结构：）

5. InsertNth 在链表的第n个位置插入一个新节点；

6. SortedInsert 给定一个有序链表，将一个新节点插入到有序链表的正确位置；

7. InsertSort 使用插入排序法为链表排序；

   提示：之前实现的SortedInsert有用了：）

8. Append 挂接两个链表；

9. FrontBackSplit 将一个链表分割成大小相等的两个链表（对于原链表大小为奇数的情况，分割为大小只相差1的两个链表）；

10. RemoveDuplicates 给定一个有序链表，其中含有重复节点，删除链表中的重复节点，使得每个不同值的节点只有一个；

11. MoveNode 给定两个链表，Pop出第二个链表的元素，Push进第一个链表；

    注意：这里的Pop和Push可以根据实际场景使用4中的任意一组定义

12. AlternatingSplit 给定一个链表，将他分割成两个链表，其中奇数位置的节点在一个链表，偶数位置的节点在另一个链表；

    提示：之前实现的MoveNode有用了：）

13. ShuffleMerge 给定两个链表，将这两个链表合并成一个链表，其中一个链表的元素在奇数位，另一个链表的元素在偶数位；

    提示：之前实现的MoveNode有用了：）

14. SortedMerge 给定两个有序链表，将他们合并成为一个有序链表；

    提示：之前实现的MoveNode有用了：）

15. MergeSort 对链表进行归并排序

    提示：实现了FrontBackSplit和SortedMerge，是不是觉得很简单：）当然，也可以尝试一下自底向上的归并排序（非递归的归并排序）。另外，对MergeSort的一个经典优化，是递归到达小数据量的时候，转而使用插入排序法。此时，我们自己写的InsertSort也有用了：）

16. SortedIntersect 给定两个有序链表，返回一个新链表，新链表中的元素是给定两个链表的公共元素。

    提示：以这个方法为基础，可以封装基于链表的集合类。大家也可以思考一下如何实现其他集合操作，如Union(合并)，Diff(差集)等等。

17. Reverse 反转一个链表

18. RecursiveReverse 使用递归的方式反转一个链表

    提示：最后特意将递归方式翻转链表列出来，是因为这个问题实在是太经典了，充分体现了和链表相关算法的美丽：）

祝大家早日“链表通关”！

---

不管是否给我赞，都请加油！