type
status
password
date
slug
summary
category
URL
tags
icon
下面是本文所要用到链表节点的定义：
增删改
1. 在O(1)时间删除链表节点
题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。[Google面试题]
分析：最常规的做法是从链表的头结点开始，顺序查找要删除的结点，找到之后再删除。由于需要顺序查找，时间复杂度自然就是了。我们试着换一种思路，将下一个节点的值赋值给需要删除的节点，然后删除下一个节点。如果需要删除的节点是最后一个节点（
target->next == null），则需要从头遍历列表找到target节点的上一个节点，然后删除。这样也是满足的时间复杂度的：假设链表总共有n个结点，我们的算法在n-1种情况下时间复杂度是，只有当给定的结点处于链表末尾的时候，时间复杂度为。那么平均时间复杂度，仍然为。
代码如下：
203. Remove Linked List Elements：删除链表中，等于val的节点
19. Remove Nth Node From End of List：
- 快慢指针维护一个长度为n的滑动窗口
节点覆盖型
- 往往删除单链表的一个节点，需要有头节点或者前一个节点来绕过删除的节点，这道题只给了要删除的节点(单链表拿不到previous的节点)，只能通过节点覆盖来做。
遍历链表
2. 单链表的转置
题目描述：输入一个单向链表，输出逆序反转后的链表
分析：链表的转置是一个很常见、很基础的数据结构题了，非递归的算法很简单，用三个临时指针 pre、head、next 在链表上循环一遍即可。递归算法也是比较简单的，但是如果思路不清晰估计一时半会儿也写不出来吧。
下面是循环版本的链表转置代码：
下面是递归版本的链表转置代码：
3. 求链表倒数第k个节点
题目描述：输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾指针。
分析：设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。
代码如下
4. 求链表的中间节点
题目描述：求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。
分析：此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第3题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。
代码如下：
21. Merge Two Sorted Lists
- DummyNode的使用
23. 合并K个升序链表 - 使用的是python不是python3
每次合并都需要从k个链表中找到
val最小的节点，所以算法使用 Python 的小顶堆 heapq 最合适。环
5. 判断单链表是否存在环
题目描述：输入一个单向链表，判断链表是否有环？
分析：通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。
快慢指针
HashSet
6. 找到环的入口点
题目描述：输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？
解题思路： 由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当 p1 和 p2 再次相遇的时候，就是环路的入口了。
为什么？：假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步。那么有：
p1走的路径：
a+b ＝ n；
p2走的路径： a+b+k*L = 2*n； p2 比 p1 多走了k圈环路，总路程是p1的2倍根据上述公式可以得到
k*L=a+b=n显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。相交点M与环入口点的距离为b，也就是说此前p1、p2相遇并走了b步。所以n步中只有前 n-b=a 步 p1 和 p2 走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。快慢指针：
HashSet
287. 寻找重复数 - 重点题目
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
Array里index, value中把value当作"next"的index，就可以把问题转化成了Linked List II(比较难想到)
7. 编程判断两个链表是否相交
题目描述：给出两个单向链表的头指针（如右图所示），比如A、B，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。
解题思路：进一步考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断两个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。这样我们就得到了一个时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N)，空间复杂度为O(1)。
代码如下：
8. 扩展：链表有环，如何判断相交-重点
题目描述：上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?上面的方法还同样有效么?
分析：如果有环且两个链表相交，则两个链表都有共同一个环，即环上的任意一个节点都存在于两个链表上。因此，就可以判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
代码如下：
9. 扩展：两链表相交的第一个公共节点
题目描述：如果两个无环单链表相交，怎么求出他们相交的第一个节点呢？
分析：采用对齐的思想。计算两个链表的长度 L1 , L2，分别用两个指针 p1 , p2 指向两个链表的头，然后将较长链表的 p1（假设为 p1）向后移动
L2 - L1个节点，然后再同时向后移动p1 , p2，直到 p1 = p2。相遇的点就是相交的第一个节点。代码如下：
10. 总结
可以发现，在链表的问题中，通过两个的指针来提高效率是很值得考虑的一个解决方案，所以一定要记住这种解题思路。记住几种典型的链表问题解决方案，很多类似的题目都可以转换到熟悉的问题再解决。