反转链表类
NO1. 反转链表
给定一个长度为 n 的链表，反转该链表，输出表头。
方法一：迭代法（推荐使用）
算法流程：
- step 1 ：特殊情况判断，空链表或只有一个结点的链表，直接返回头结点；
- step 2 ：设置两个指针
cur和prev，cur指向当前结点，prev指向上一个结点（初始为 null）； - step 3 ：遍历整个链表，每到一个结点，断开当前结点
cur与下一个结点cur.next的指针，并用临时变量temp记录下一个结点，然后当前结点的next指向上一个结点（实现反转）；- 轮换
cur与上一个结点prev，进行下一个结点反转； - 循环退出条件为
cur == null；
- 轮换
- step 4 ：返回
prev（反转后，原尾节点变成头结点）；
代码实现：
public class Main {
public ListNode ReverseList(ListNode head) {
// 特殊情况判断
if(head == null || head.next == null) return head;
// 双指针
ListNode prev = null, cur = head;
while(cur != null) {
ListNode temp = cur.next; // 断开链表，要记录后续⼀个
cur.next = prev; // 当前的next指针指向前⼀个
prev = cur; // 前⼀个更新为当前
cur = temp; // 当前更新为刚刚记录的后⼀个
}
}
}
复杂度分析：
- 时间复杂度：\(O(N)\)，遍历链表一次；
- 空间复杂度：\(O(1)\)，申请常数个变量；
方法二：递归
根据迭代法，每当我们反转链表中某个结点以后，要遍历进入下一个结点进行反转，相当于对后面的子链表进行反转，那这就是一个子问题，因此我们可以使用递归来解决。
- 终止条件：当到达链表尾部，要么当前指针为空，要么下一个指针为空，直接向上层返回当前结点；
- 返回值：每一层向上一层返回翻转后子问题的头结点；
- 本层任务：先进入后一个结点作为子问题，继续反转，然后记录返回的头结点，连接在本层结点的后面；
算法流程：
- step 1 ：递归向下遍历链表，直到遍历到最后一个结点；
- step 2 ：往上一次逆转两个结点；
- step 3 ：逆转后的尾连接本层的结点
head，并断开两节点的原指针（置为 null）；
public class Main {
public ListNode ReverseList(ListNode head) {
// 递归停止条件
if(head == null || head.next == null) return head;
ListNode newHead = ReverseList(head.next); // 反转下一个
// 本层任务，如
head.next.next = head;
head.next = null;
return newHead;
}
}
复杂度分析：
- 时间复杂度：\(O(N)\)，遍历链表一次；
- 空间复杂度：\(O(N)\)，递归栈的深度就是链表的长度\(N\)；
NO2. 链表内指定区间反转
将一个结点为 size 的链表 m 位置到 n 位置之间的区间反转；
链表其他部分不变，返回头结点；
方法一：头插法迭代（推荐）
第一步肯定是要先找到第 m 个位置，然后不断反转，直到到达 n 位置；由于m可能为1，即头结点，那反转之后 head 就不再指向头结点了，所以，先构造一个虚拟头结点；
算法流程：
- step 1 ：可以在链表头添加一个虚拟头结点，后续返回时去掉就好了；
- step 2 ：使用两个指针，
cur指向当前结点，prev指向前驱节点； - step 3 ：依次遍历链表，到达第 m 个位置；
- step 4 ：从 m 到 n 位置的结点，依次断掉指向下一个结点的指针，指向前驱，实现反转；
- step 5 ：返回虚拟头结点的
next；
代码实现：
public class Solution {
public ListNode reverseBetween (ListNode head, int m, int n) {
// 虚拟头结点
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 双指针（反转链表常规操作）
ListNode prev = dummy, cur = head;
// 找到第 m 个结点
for(int i = 1; i < m; i++) {
prev = cur;
cur = cur.next;
}
// cur 指向 m，开始反转
for(int i = m; i < n; i++) {
ListNode tmp = cur.next;
cur.next = tmp.next; // 1
tmp.next = pre.next; // 2 开始头插到 pre 后面
pre.next = tmp; // 3
}
return dummy.next;
}
}
复杂度分析：
- 时间复杂度：\(O(N)\)，最坏情况下，需要遍历链表一次；
- 空间复杂度：\(O(1)\)，申请常数个变量；
方法二：递归
算法流程：
- step 1 ：先利用递归找到反转区间的起点；
- step 2 ：再利用递归从第 n 个位置开始反转，往上拼接；
代码实现：
public class Solution {
public ListNode reverseBetween (ListNode head, int m, int n) {
// 找到第 m 个结点，执行反转
if(m == 1) return reverse(head, n);
// 找 第 m 个结点
ListNode node = reverseBetween(head.next, m - 1, n - 1);
head.next = node; // 拼接已翻转
return head;
}
ListNode tmp = null; // tmp用来暂存第n个结点的后继
public ListNode reverse(ListNode head, int n){
// 递归停止
if(n == 1) {
tmp = head.next;
return head;
}
ListNode node = reverse(head.next, n - 1); //进⼊⼦问题
head.next.next = head; //反转
head.next = tmp; //拼接
return node; // 返回上一层
}
}
复杂度分析：
- 时间复杂度：\(O(N)\)，最坏情况下，需要遍历链表一次；
- 空间复杂度：\(O(N)\)，最坏情况下，递归栈的深度就是链表的长度\(N\)；
NO.3 链表结点每K个一组翻转
给定一个链表，从头开始每 K 个作为一组，将每组的链表结点翻转；
组与组之间的位置关系保持不变；
如果最后链表末尾剩余不足 K 个结点，则不反转，直接放在尾部；
方法一：头插法迭代
算法流程：
- step 1 ：反转过程中要改变 head 指针，就得设个虚拟头结点，定义双指针
pre和cur； - step 2 ：统计链表总长度
len，用于得出翻转组数len / k； - step 3 ：外循环控制翻转组数，内循环控制组内的k个结点翻转（头插 k - 1次）
代码实现：
public class Main {
public ListNode reverseKGroup (ListNode head, int k) {
// 特判
if(head == null || head.next == null || k < 2) return head;
// 要改变头结点的，就得设个虚拟头结点
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 双指针，基本操作
ListNode pre = dummy, cur = head;
// 统计链表总长度
int len = 0;
ListNode p = head;
while(p != null) {
len++;
p = p.next;
}
// 翻转组数，仅翻转 len / k
for(int i = 0; i < len / k; i++) {
// 外循环控制组数，内循环控制组内的k个结点翻转（头插 k - 1次）
for(int j = 1; j < k; j++) {
// 把一组内的结点 temp 头插到 pre 后
ListNode temp = cur.next;
cur.next = temp.next;
temp.next = cur;
pre.next = temp;
}
// 一组翻转完成，去下一组，
pre = cur; // pre 指向上一组尾结点 cur
cur = cur.next; // cur 指向下一组的第一个结点
}
return dummy.next;
}
}
复杂度分析：
- 时间复杂度：\(O(N)\)，需要遍历链表两次；
- 空间复杂度：\(O(1)\)，申请常数个变量；
方法二：递归
终止条件：当进行到最后一个分组，元素个数不足 k 个，就将剩余的最后一个分组直接返回给上层；
返回值：每一层要返回给上层的是翻转后这个分组的头结点，并且后面已经连接好了所有的已翻转好的分组链表；
本层任务：先遍历 k 次，找到该分组尾结点的位置，然后从分组的头结点遍历到尾结点，依次翻转；
算法流程：
- step 1 ：翻转前，找到每次分组的尾节点的下一个结点，即下一分组的头结点
- step 2 ：采用常规的翻转链表操作；
- step 3 ：递归进行拼接；
代码实现：
public class Main{
public ListNode reverseKGroup (ListNode head, int k) {
ListNode tail = head;
// tail指向本组尾节点的下一个节点，即下一分组的头结点
for(int i = 0; i < k; i++) {
// 最后一分组不足 k 个结点，直接向上层返回 head
if(tail == null) return head;
tail = tail.next;
}
// 常规的翻转链表操作
ListNode pre = null, cur = head;
while(cur != tail) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
// 当前尾指向下⼀段要翻转的链表
head.next = reverseKGroup(tail, k);
//
return pre;
}
}
复杂度分析：
- 时间复杂度：\(O(N)\)，一共遍历链表 n 个结点；
- 空间复杂度：\(O(1)\)，申请常数个变量；
总结
链表反转类算法题，有两种解决思路：
- 遍历链表，利用两个滚动指针，不断改变当前结点的
next指针的指向（当前结点的next指向前驱），每次改变指针时都要暂存下一个节点； - 头插法，每次把结点头插到
prev指针后，实现反转；