链表和双指针框架
- 前后指针:方便链表删除
- 快慢指针:获取链表倒数第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:递归实现双向遍历
单链表只能单方向遍历,可以利用递归,对其进行正反两个方向的遍历。
其实递归就是自动维护了一个栈,用迭代的方式就是遍历链表时,节点入栈,链表遍历结束,节点出栈,形成正反两个方向的节点遍历。
例题:
- 回文链表