所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
链表题一开始要判断链表是否为空，或者只有一个元素的时候的情况。
链表题的思路：能递归就递归。
链表题的技巧： (1) 寻找符合特征的两个相邻点：可以使用两个指针一起走，判断空就是后面的指针不为空。
例如判断当前结点是不是最后一个结点：通过cur->next是否为空来每次多向后看一步。如果不为空，那就不是最后一个结点，否则就是最后一个结点。
例如寻找目标点值target的前一个点：只需判断cur->next->val是否等于target。
具体题目
206. Reverse Linked List
题意：翻转链表。
解：翻转链表非递归方法：先给链表建立dummy头，dummy头的next指向翻转后链表的头，由于链表在反转的过程中头发生移动，是在变化的，而变化之后，要保存前一个头作为当前head的next，也就是说head变化前需要保存下自己，可以建立一个pre指针来保存，也可以灵活的借助dummy的next来保存。另外，在修改当前head的next为pre时候，后面的信息会丢失，因此需要一个nex指针来保存当前head的next。
总结：非递归翻转链表，需要有两个辅助指针，一个保存已翻转链表的新head、另一个保存当前处理指针的next。循环里面的写法顺序：首先第一次循环时，pre是空的，所以赋给head的next，之前就要保存当前head的next。之后，修改pre为自己，然后自己通过nex来跳到下一个。 注意的是：翻转后的头是pre，而不是head，因为head最后会因为变成NULL而结束循环。
翻转链表递归法： 写法1: 如果头为空，或者只有一个元素，那么返回头，否则，翻转head－>next，然后返回新头（也是要return的头），期间要将head－>next的next指向head，然后head的next指向NULL(相当于删除之前的边)。
写法2: 尾递归。类似于非递归解法，函数中加入新的头临时变量，在现有的head变成NULL之后，返回新的头。翻转head－>next，head的pre依次作为新的头（从NULL开始）。显然，新的头只在当前head为NULL时候才有效。
92. Reverse Linked List II
题意：翻转链表的第m个元素到第n个元素。
解：先找到第m个元素的前一个结点pre。然后对一定长度使用206题的方法，不过要注意pre的next要修改为newhead，翻转后的部分的next要修改指向n+1元素。
两种方法：一种是使用206的翻转法，不过要把开头结尾的指针接上。
第二种是使用类似头插法来翻转链表，也就是把cur扫过的结点插入到pre的下一个结点。cur要把next取代为nex的nex，这样保证了链表仍然是连通的。
PS.链表为空，或者只有一个结点，则直接返回。
138. Copy List with Random Pointer
题意：拷贝链表，链表结点里面包含一个random指针，可以指向链表中任意一个结点。
解：此题普通解法思路：先复制每一个结点，并保存原结点和复制结点的映射关系，可以是双向的映射关系，也可以是单向的映射关系（不过那样，就需要使用临时指针使得代码处理的时候保持一致）。然后在扫描一遍新老链表，将random的信息复制过来。时间复杂度和空间复杂度都是O（n）。
优化思路是减小空间复杂度到O（1）：先把新链表每个结点插入到老链表对应结点的后面，这样就省去了hash表的空间。
141. Linked List Cycle
题意：判断链表有环。
解：方法是双指针，快指针每次走两步，慢指针每次走一步，如果二者相等，那么有环，否则，如果快指针走到头，就没有环。编码中注意空指针引用问题，初始化的返回条件是，如果一个链表为空，或者只有一个结点，那么立即返回false。快慢指针初始化为头后面的下一步，因为不能一开始让双指针就相等。
142. Linked List Cycle II
题意：141基础之上，求环的起始位置的指针，如果链表没有环，那么就返回null。
解：还是快慢指针，先找到两个指针的交叉点，然后快指针指向链表头，速度变为慢指针速度，慢指针从交叉点出发，然后相遇的点就是结果。
从快慢指针交叉点和链表头开始走的证明过程：
现在设链表起点到环起点的距离是x, 然后环内部分顺时针部分到快慢指针交叉点（交叉点一定在环里面）距离为y，后面的半段是z，环长度为r。 那么有：
（1）x + k1 * r + z表示慢指针走过的距离，快指针走过的距离是慢距离的两倍，那么是 2 * (x + k1 * r + z)。
（2）快慢指针走到同一点，意味着快指针在环上多走了几圈，所以有快慢指针相减x + k1 * r + z = k2 * r。
变形，有x + z = (k2 - k1) * r，其中 r == y + z。这样继续变形，有x = (k2 - k1 - 1) * r + y。
这个公式的意思就是，从链表起点出发到环起点和从交叉点出发到环起点是同时到达的，无论后者在环上多绕了几圈。
PS.此题注意的点： （1）快指针一次跳两步，所以链表长度为空或者为1的时候，单独考虑。
（2）发现没有环时候要提前返回，不能在继续后面找交叉点的部分了。
（3）证明过程比较重要。
160. Intersection of Two Linked Lists
题意：有两个尾部相同的链表a和b，求交叉点。两个链表相同位置上元素相同就是所要求的交叉点。
解：暴力求解就是双重循环， 也可以使用hash，但是hash消耗额外空间。
此题有个特殊技巧：使用两个指针同时移动，制造两个链表，一个是a1 + c ＋ b1 + c，另一个是b1 + c + a1 + c。 其中，a1，b1是ab链表的前缀，c是两链表的公共尾部，观察发现，第一个的前面的a1 + c ＋ b1部分等于第二个的b1 + c + a1部分。
也就是说，两个指针指向两个链表每次同时移动一步，那么走了a1 + c + b1步之后，就到达了公共部分c的开头。 其中a1 + c + b1步到底是多少步不清楚，但是知道一步步走之后绝对会到达同一个节点。
编码思路就是保持双指针分别从a和b链表开始访问，在一个链表访问完之后，跳到另一个链表的头开始访问。如果找到相等的，就返回。
注意的是，双指针在访问过程中都可以为空，也必须要轮空（如果两个链表不交叉，平行，那么不轮空将死循环）。如果都为空，说明没找到。
此题关键就是要把空算上，a + nullptr + b + nullptr和b + nullptr + a + nullptr相比较。
725. Split Linked List in Parts
题意：将一个链表切分为均等的k段，分的不均匀的时候稍长的放前面。
解： 先看如何划分，对于长度为10的链表，划分是4，3，3，而对于长为11的链表来说是4，4，3。所以得出的结论就是分的段，最少长度是len/k，而最前面的有len%k个段比后面的段多1。 接下来，就是链表操作，切断就是把每段的头加入结果，并将每段结尾元素的next置为空。
23. Merge k Sorted Lists
题意：k路归并。
解：方法一：写一个二路归并，然后对数组进行两两归并。可以优化的地方在于，两两归并的时候，要优先两两归并原数组的两个元素，虽然表面上看二路归并的时间复杂度是O（m+n），但是这样会比较快。
方法二：使用优先级队列。建立一个小的元素处于堆顶”小根堆“。然后，分别将K路的链表的头结点放入这个”小根堆“优先级队列，然后，每次从堆顶弹出一个元素作为合并后链表的值，然后将该元素的下一个元素（如果不为空）入队。这样一步步的构建，直到队列为空。
445. Add Two Numbers II
题意：Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
解：方法一：翻转之后相加。方法二：使用栈。然后弹出一个个加。
25. Reverse Nodes in k-Group
题意：按照k个一组，翻转，如果最后一组不足k长度，则最后一组不翻转。
解：此题思路是：翻转k个，返回翻转k个链表的末尾。
一开始使用dummy结点来模拟上一个空的翻转k链表末尾。然后每次向后找到第一个结点和第k+1个结点。
翻转第1到第k个结点，之后，将上一个链表的末尾指向中间翻转链表的开头，中间翻转链表的末尾指向第k+1个结点。最后返回链表末尾。
369. Plus One Linked List
题意：此题要把数字链表的尾加1。
解：方法有多种。一种是使用栈，先把扫到的指针存到栈里，然后对栈进行弹栈处理，如果最后的carry不为0，那么新建node，插入head的前面并返回newhead。
还有一种是使用递归，把剩余的部分当作已经加过1来看，并返回是否存在carry，最后对第一个carry处理就好了。
还有一种方法是，先找右边开始数第一个不为9的数字，具体方法就是扫描一遍，看不等于9的就记录下来。找到之后，对于他加1，然后把右边全9部分变为0，返回；
如果找不到不为9的数，那么说明全部是9，那么加入新结点1，然后把其余数字都置为0。
817. Linked List Components
题意：给出一个链表和一个数组，现在问数组中的数组成了链表中几个连通的小部分。
解：此题不需要太纠结，只需要将数组存入hash表，然后对链表扫描一遍就可以知道有几个连通部分了。
扫描时候，如果当前点在hash表中，但是下一个点却不在hash表中，那么说明连通断了，也就是说之前的算一个连通，然后扫描，继续找下一个在hash表中的情况，如果都存在那么继续扫描。相当于在原来链表找到连通部分的结尾。
24. Swap Nodes in Pairs
题意：两两交换链表相邻结点，例如1->2->3->4变为2->1->4->3。
解：使用递归求解，当链表只有一个元素或者没有元素时候，递归结束，否则，先翻转除了前两个元素的后面部分，然后把后面部分接到第一个元素的后面，然后将第二个元素指向第一个元素，最终返回第二个元素。
708.Insert into a Cyclic Sorted List
题意：插入有序的单循环链表，单循环链表的头不能变，且允许插入相同元素。要求插入后维持有序性质。
解：链表插入操作，思路就是，首先链表为空的时候，单独处理，返回新的头结点，因此插入函数的返回值类型是Node*。
其次，对于不为空的链表，循环一次，一定就能够找到插入点，所以首先要保证我们可以不死循环的访问一遍链表。
再次，就是对插入的点进行考虑，分情况讨论，此题使用两个指针一起扫描，尝试插入两个指针之间，
如果两个指针指向元素是递增的pair，那么我们看插入的值是否介于二者之间，如果是，那么插入，如果不是，那么继续。如果是递减的pair，说明遇到了有序情况中最大值翻转到最小值的情况了，那么此时如果插入的值比pair第一个元素大，那么可以插入，或者插入的值比pair的第二个元素小，那么也可以插入，其他情况下不插入。
最后，考虑特殊情况，此题特殊情况就是链表中的值全部相等，全部相等的时候，有序情况中最大值翻转到最小值的情况变得不明显，难以区分。但是此时就是任意一个地方插入就可以了。
328. Odd Even Linked List
题意：把链表的奇数部分结点放到链表前面，偶数部分放到后面。
解：先找到奇偶链表的头部，然后把各自链表建立，然后把偶链表的头接到奇链表的后面。
