先上好货, 来自
们的总结。
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
（这个我没怎么看）
java
大总结：
http://blog.csdn.net/fightforyourdream/article/details/16353519
Yu牛人笔记：
https://www.zybuluo.com/smilence/note/128
=======================转载结束==============================
主要会对这三个资源中出现的链表题目总结
代号LC
代号CC
代号EPI （optional）
=============================================================
LeetCode中的链表题目根据考察点或解题方法可以分为以下几个类别：一共24道题目。希望大家看完这篇总结都能轻松解答这24道题目。
- ===== Remove=====
[LC]
Remove Duplicates from Sorted List
题目：删除有序单链表中重复元素，令每个元素只出现一次。
思路: 维护pre和cur。pre指向当前的不重复的最后一个元素（有可能马上就又重复了），cur进行依次扫描，当遇到了非重复的元素时就更新pre.
其他：
[LC]
Remove Duplicates from Sorted List II
题目：删除有序单链表中，所有出现了重复的元素 ，令其他元素只出现一次。
（输入 1-
>
2-
>
3-
>
3-
>
4-
>
4-
>
5, 返回1-
>
2-
>
5）
思路：维护pre和cur,思路和I很相似，只是pre指向上一个最后的不重复元素（已经被确认过不重复的元素）。
其他：
小结：
LeetCode还有两个轻松变型：
[LC]
Remove Duplicates from Sorted Array I
[LC]
Remove Duplicates from Sorted Array II
- =====双指针=====
全名是：双指针定位大法
第一次听说，双指针是在peking2二爷的LeetCode难度系数表里。后来在cc150里链表那一章看到了walker/runner方法。
我们最关心的2个指针如何变化。（我习惯叫slow/fast）
[LC]
题目：判断单链表里是不是有环。
思路：可以用额外空间HashTable做，也可以用walker/runner（双指针）做
点评：这题不难，但有时候拎不清。
说得通俗一点，如果链表有环，那么一个指针遍历该链表，就进入了无限循环，走不到头。
那么我们用两个指针呢？这两个指针一快一慢一定会在环中相遇。（请画图, 这是这道题的核心原理）
所以初始条件slow = fast = head. 终止条件是fast = null 或fast.next = null
fast = null的意思是快节点已经离开链表了。fast.next = null 为快节点到达链表尾节点。
如果中间slow和fast相等了，说明有环。其他情况均无环。
[LC]
题目：判断单链表里是不是有环，并返回环的起始点。
思路： 用walker/runner（双指针）做，还涉及到一个数学公式
其他：Cc150里也有。
[LC]
Remove Nth Node From End of List
题目： 删除单链表里倒数第N个节点并返回头节点。
思路：关键点就是如何找到倒数第N个节点，用walker/runner（双指针）做
其他： Cc 150里一个很类似的题目，找到链表的倒数第k个节点。
[LC]
题目： 将链表右旋k个节点。
思路：用双指针法定位到待旋转点，然后把下一个节点设置为新表头，把当前节点设置为表的尾部。
其他：可以和旋转数组放在一起理解
小结：
双指针法不局限于在链表中使用，在许多数组题目和处理字符串的题目里，双指针法的使用可以将时间复杂度下降到O(n).
（例子以后再补充）
- ===== Reverse=====
[基础题]
题目：反转全部链表
思路：维护 pre, cur, next指针。
pre指向当前节点的前驱节点。next指向当前节点的后继节点。
[LC]
题目：反转部分链表，从位置m到位置n.
思路： 首先，找到位置m, 然后进行反转直至到达位置n.
[LC]
题目：给定单链表，以2个为一对反转链表 。输入
1-
>
2-
>
3-
>
4 返回 2-
>
1-
>
4-
>
3
思路：维护pre, cur,next指针。Next指向下一个待reverse对的节点。Pre指向已经reverse好的最后一个节点。
[LC]
题目：给定单链表，以k个为单位反转链表
思路：先对已visit的节点计算数量，到达k就把前k个节点reverse.
注意：到达k才reverse, 不到达k不需要。
小结：
反转链表中是一个重要操作。要好好掌握。
LeetCode中虽然没有一个题目要求从头到尾直接反转链表。但是这些题目都是在反转链表这个操作上考的。
最基础的方法，reverse(ListNode head)或 reverse(ListNode head, ListNode pre, ListNode next)一定要能很快且无bug的写出来。
- ===== Sort=====
[LC]
题目：在链表中实现排序。要求O(nlogn)
思路：归并 mergesort，双指针(walker/runner)
其他：也可以用其他符合时间的排序操作。
[LC]
题目：在链表中实现插入排序
思路：和插入排序一样，双指针(pre/next)
其他：
[LC]
题目：把链表中小于元素x的节点放在x前，大于x的节点放在x后
思路：和快排 quicksort的Partition操作类似，还用了双指针（walker/runner）。
其他：
[LC]
题目：合并两个有序单链表。
思路：和MergeSort里的Merge操作类似
[LC]
题目：合并k个有序单链表并返回1个有序单链表
思路：可以将Merge Two Sorted Lists作为subroutine。使用分治法把k个链表分成两半，然后两两归并，直到最后剩下两个链表就合并结果。
其他：可以用其他数据结构（heap）来优化
小结：
- 在链表上实现排序，感觉这种题能让大家进一步体会到链表和数组的区别。
- 合并在链表中是一个典型操作。要好好掌握。类似的题目是一维数组的合并。
=====模拟数值运算=====
[LC]
已有讨论帖，
传送门[传送ing]
=====树=====[待总结]
[LC]