链表和双指针框架
- 前后指针：方便链表删除
- 快慢指针：获取链表倒数第N个元素
- 快慢指针 + 前后指针：组合问题
- 快慢指针：相交、判环、起点、长度
- 双索引指针：合并/分割/拼接链表
- 链表处理细节
- 细节1：创建额外的哨兵节点的时机
- 细节2：链表递归顺序
- 细节3：虚拟节点
- 细节4：递归实现双向遍历
前后指针：方便链表删除
力扣的链表问题，基本都是单链表。
单链表的操作难点在于，缺了指向前一个节点的指针，而链表删除结点是通过待删除结点的前一个结点。
在力扣里，是让遍历的指针p，从指向【当前节点】改成指向【前一个节点】，这样就有了指向前一个节点的指针。
每次查看节点从 p 变成 p.next，循环终止条件从 p == NULL 变成 p.next==NULL。
如果只是遍历问题，这样写OK，但是通常链表问题除了需要寻找到某个特定项元素。
查之外还需要增/删/改，而增/删/改或者实现一定程度的逆向遍历，都需要额外的指针索引。
这样叠加操作比较别扭且容易出错。
我们寻找一种更通用的设计方法，这称为【链表和前后指针框架】。
当删除链表结点时，既需要访问当前结点，也需要访问前一个结点。
就使用两个指针来遍历链表，curr 指针指向当前结点，prev 指针指向前一个结点。
这样两个指针的语义明确，也让你写出的代码更易理解。
ListNode pre = null; // 辅助指针，记录 cur 的上一个值
ListNode cur = head; // 主指针，cur 表示当前结点
while (cur != null) {
if (prev == null) {
// curr 是头结点时的操作
} else {
// curr 不是头结点时的操作
}
pre = cur; // 循环中始终维护 pre 是 curr 的前一个节点
cur = cur.next; // 更新 cur
}
链表使用前后指针遍历框架：
- 判断问题是否为链表遍历-修改，如果是，套用链表遍历框架
- 思考单步操作，将代码加入遍历框架
例题：
- [206].反转链表
- [203].移除链表元素
- 两数相加 II
- 反转链表 II
快慢指针：获取链表倒数第N个元素
链表数据类型的特点决定了只能单向顺序访问，而不能逆向遍历或随机访问。
我们可使用快慢指针的技巧来实现一定程序的逆向遍历。
比如获取中间项：
快指针速度是慢指针速度两倍，快指针移动到末尾时，慢指针指向中间节点。
自定义返回类型 middleNode(ListNode head) { // 获取链表中间项元素
ListNode slow = head, fast = head; // 快慢指针初始化指向 head
while (fast != null && fast.next != null) { // 快指针走到末尾时停止
slow = slow.next; // 慢指针走一步
fast = fast.next.next; // 快指针走两步
}
return 自定义返回内容; // 快指针在终点，慢指针在中点
}比如获取倒数第N项：
快指针提前走n步，此时快慢指针之间间隔n-1步，快慢指针再一起走，当快指针走到链表尾部的时候，慢指针指向的就是第n个元素。
ListNode removeNthFromEnd(ListNode head, int k) {
ListNode fast = head;
for (int i = 0; i < k; i++) // 将 fast 前进 k 个元素
fast = fast.next; // 这里省略了检测空指针的代码
// fast 和 slow 指针间隔 k 个同时前进
// 这里使用了前后指针，将慢指针 slow 变成两个指针 cur 和 pre
ListNode cur = head;
ListNode pre = null;
while (fast != null) {
prev = curr;
curr = curr.next;
fast = fast.next;
}
if (prev == null)
head = curr.next;
else
prev.next = curr.next;
return head;
}例题：
- [19].删除链表的倒数第 N 个节点
- [141].判断链表是否有环
- 环形链表 II
- 排序链表
- 链表的中间结点
快慢指针 + 前后指针：组合问题
链表组合问题，如先查链表中间节点（特定项），再删除这个节点。
- 特征1：特定项，对应方法是快慢指针
- 特征2：删除，对应方法是前后指针
我们融合这俩种方法，使用三个指针即可，分别是快指针、慢指针、慢指针的前一个指针。
这样当快指针到达链表尾部时，慢指针的前一个结点正好是我们要删除的指针。
快慢指针：相交、判环、起点、长度
判断环：给出一个链表头结点，判断是否存在环。
- 使用快慢指针，快指针一次走两步，满指针一次走一步，如果快慢指针能够再次相遇（相交），则说明有环，反之则无环。
环起点：给出一个链表头结点，如果链表有环，则返回入环的第一个节点；如果无环，则返回null
- 使用快慢指针，先判断是否存在环。如果存在环，则将快指针指向头结点，然后快慢指针每次都各走一步，再次相遇的节点，就是入环的第一个节点。
环长度：给出链表的头结点，假设该链表存在环，求出环长和入环前的长度。
- 使用快慢指针，当快慢指针相遇时；
- 计算环长，使快指针暂停，慢指针继续走，并计数，当再次相遇时，慢指针走的周长即环长；
- 计算入环前长度，使快指针指向头结点，快慢指针每次各走一步，当快慢指针再次相遇时
- 快指针走的步数即为入环前的长度。
160.相交指针：给两个单链表的头指针headA和headB，找出相交的起始节点，如果不相交则返回null。
用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，怎么让 p1 和 p2 能够同时到达？
我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样俩个指针走的速度、走的距离都是一样的，肯定会同时抵达终点。
- 特征：有相交，方法：快慢指针数步子
双索引指针：合并/分割/拼接链表
计算机区分和找到目标-编号：人类区别/指挥于其他人/事物的特质是给人起名字的，计算机是通过编号，数据的操作，都是先找到盒子的地址，然后把那个盒子中的数据拿出来处理，处理完的内容，再放回到某个地址中。
21.合并两个有序链表
- 特征：合并俩个链表成一个，方法：双索引指针
- 分隔链表
- 特征：一个链表分割俩个，方法：双索引指针
- 合并 k 个有序链表
- 特征：给的是数组链表，里面有k个链表，合并k个链表，方法：k索引指针改为用优先队列存储k个索引
链表处理细节
细节1：创建额外的哨兵节点的时机
当需要创造一条新链表的时候，可使用虚拟头结点简化边界情况的处理。
例题：
- 21.合并两个有序链表，把两条有序链表合并成一条新的有序链表。
- 86.分隔链表，把一条链表分解成两条链表。
细节2：链表递归顺序
void traverse(ListNode root) { // 递归遍历单链表
if (root == null) return; // 最基础的情况
print(root.val); //【前序位置】
traverse(root.next);
print(root.val); //【后序位置】
}前序位置和后序位置的区别是什么？
- 前序位置的
print(root.val)：遍历链表，沿途输出节点，顺序遍历 - 后序位置的
print(root.val)：遍历链表，一直遍历，直到遇到最基础的情况才能计算出子问题的解，逆序遍历。
细节3：虚拟节点
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。
头结点的尴尬，因为头结点没有前一个节点了。
每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。
什么时候需要用虚拟头结点？
当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。
- 把两条有序链表合并成一条新的有序链表
- 把一条链表分解成两条链表
细节4：递归实现双向遍历
单链表只能单方向遍历，可以利用递归，对其进行正反两个方向的遍历。
其实递归就是自动维护了一个栈，用迭代的方式就是遍历链表时，节点入栈，链表遍历结束，节点出栈，形成正反两个方向的节点遍历。
例题：
- 回文链表