51工具盒子学而时习，本文记录链表操作相关算法练习笔记。
反转链表 {#反转链表}
题目描述 {#题目描述}
输入一个链表，反转链表后，输出新链表的表头。
解题代码 {#解题代码}
复杂度 {#复杂度}
| 时间 | 空间 | |------|------| | O(n) | O(1) |
解题备注 {#解题备注}
- 维护当前节点，顺带考虑前后节点，会比较稳健
- 设置虚拟前置节点，现场生成后置节点，更加鲁棒，甚至同时囊括了输入为None的情况
- 需要注意返回前置节点作为新链表头
两个链表是否相交 {#两个链表是否相交}
这个问题有意思，也是力扣第 160 题「相交链表open in new window」函数签名如下：
给你输入两个链表的头结点 headA 和 headB，这两个链表可能存在相交。
如果相交，你的算法应该返回相交的那个节点；如果没相交，则返回 null。
比如题目给我们举的例子，如果输入的两个链表如下图：
那么我们的算法应该返回 c1 这个节点。
这个题直接的想法可能是用 HashSet 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间。
如果不用额外的空间，只使用两个指针，你如何做呢？
难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应：
如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时 走到公共节点，也就无法得到相交节点 c1。
解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。
所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。
如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：
那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？
这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。
判断链表是否包含环 {#判断链表是否包含环}
判断链表是否包含环属于经典问题了，解决方案也是用快慢指针：
每当慢指针 slow 前进一步，快指针 fast 就前进两步。
如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。
当然，这个问题还有进阶版，也是力扣第 142 题 环形链表：如果链表中含有环，如何计算这个环的起点？
可以看到，当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
为什么要这样呢？这里简单说一下其中的原理。
我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：
fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。
假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。
巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走k步可以转回到相遇点，那走 k - m 步肯定就走到环起点了：
所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。
删除链表的倒数第 N 个结点 {#删除链表的倒数第-N-个结点}
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
合并两个有序链表 {#合并两个有序链表}
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
分隔链表 {#分隔链表}
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
链表的中间结点 {#链表的中间结点}
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
合并 K 个升序链表 {#合并-K-个升序链表}
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
206. 反转链表 {#206-反转链表}
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
92. 反转链表 II {#92-反转链表-II}
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
参考资料 {#参考资料}
文章链接：
https://www.zywvvd.com/notes/study/algorithm/list/about-list/
