链表

由于链表的结构特殊，没有像数组那样方便的库方法，因此其很多操作都需要用到底层算法解决。（不过也因此可以巩固一下）

例如需要手写排序操作。

排序

根据链表的类型可选择不同的排序算法。

单链表

如果要保持时间复杂度 O(nlogn)，则需要使用分治策略（归并排序），拆分链表。（详细算法实现参照排序一文）

其中 n 是链表长度。

双向链表

双向链表既可以从前遍历，又可以从后遍历，所以不只可以使用归并排序，还可以使用快速排序。（我猜的，暂未进行实践）

技巧

寻找中间节点：快慢指针，找到 mid 后再根据需求是否断链（前指空）。
dummy 节点：快速返回新的链表。
寻找倒数第 n 个节点：前后指针，前指针走 n 步，然后两个指针再一起走。