从今天开始进行高频算法的训练，一方面训练自己的逻辑思维，一方面保持自己的竞争力。训练过程有这么两个基准原则：
- 首先训练题的来源呢有三个，首选的是三个都出现过的高频题，以：牛客101为基准分类，然后在CodeTop中找近一年内出现频率最多的牛客中该分类的题目，还有就是LeetCode热题100，这个按照最低参考度考虑。
- 其次同一篇Blog里记录相关性较强的题，可以理解为普通-升级-再升级。例如当前这篇：反转链表-区间反转链表-K个一组反转链表
废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！首先，链表对应的数据结构在这篇Blog中：【基本数据结构 一】线性数据结构：链表，基于对基础知识的理解来进行题目解答。
反转链表
首先来个最简单的反转链表
题干
输入输出示例：
输入：
{1,2,3}
返回值：
{3,2,1}
输入：
{}
复制
{}
说明：空链表则输出空
解题思路
迭代方式，比较简单，就是用双指针一直向后滑动，将引用方向反转，特别需要注意的是，由于下一个节点会因为在反转过程中断掉，所以需要用临时节点记录下一个节点的位置。
解题代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
// 1 如果为空列表，返回null
if (head == null) {
return null;
}
// 2 定义双指针
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
// 存储下一个节点
ListNode pNext = cur.next;
// 当前节点指向上一个[局部反转]
cur.next = pre;
// 双指针向后移动
pre = cur;
cur= pNext;
}
return pre;
}
}
时间复杂度O(N)：遍历了一遍链表； 空间复杂度O(1)：常数级空间
链表内指定区间反转
升级版，链表内指定区间进行反转
题干
输入：
{1,2,3,4,5},2,4
返回值：
{1,4,3,2,5}
输入：
{5},1,1
返回值：
{5}
解题思路
头插法迭代方式，增加如下几个节点或节点指针：
- dummy 原始链表头节点的虚假头节点，为了避免当head节点位置改变且无明确位置的指针节点不知道该如何返回的情况
- pre指向反转区间前一个节点
- cur指向遍历到的位置（虽然他的位置在移动，但是其实一直指向的是同一个节点，即原始链表m处的节点）
- pNext 指向cur下一个节点，反转过程就是将这个节点插入到pre的下一个位置
步骤主要分为两大步骤
- pre和cur同时向后走m步到达要反转的列表区间，pre指向反转区间前一个节点，cur为当前反转子区间的头节点
- 进行n-m次的节点反转，每次反转目标都是将pNext移动到pre的后边，分三步
这三个步骤是：
cur.next = pNext.next;: cur指向下一个待转节点pNext.next=pre.next: pNext节点指向反转子区间的尾节点，成为反转子区间新的尾节点pre.next=pNext: pre指向反转子区间新的尾节点pNext
整体示意图如下：
解题代码
Java版本实现
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
if (head == null) {
return null;
}
// 1 设置虚拟头节点[避免当head节点位置改变且无明确位置的指针节点不知道该如何返回的情况]
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 2 双指针向后移动m步
ListNode pre = dummy;
ListNode cur = head;
for (int i = 1; i < m; i++) {
pre = cur;
cur = cur.next;
}
// 3 m到n的区间链表要进行反转[下一个节点和已反转的子区间整体进行反转]
for (int i = m; i < n; i++) {
// 1 pNext 指向cur下一个节点，反转过程就是将这个节点插入到pre的下一个位置
ListNode pNext = cur.next;
// 2 cur指向下一个待转节点
cur.next = pNext.next;
// 3 pNext节点指向反转子区间的尾节点，成为反转子区间新的尾节点
pNext.next = pre.next;
// 4 pre指向反转子区间新的尾节点pNext
pre.next = pNext;
}
return dummy.next;
}
}
时间复杂度O(N)：遍历了一遍链表； 空间复杂度O(1)：常数级空间
链表中的节点每k个一组翻转
ok，接下来难度再升级
题干
输入：
{1,2,3,4,5},2
返回值：
{2,1,4,3,5}
输入：
{},1
返回值：
{}
解题思路
递归方式，我们这时候可以用到自上而下再自下而上的递归或者说栈。如果这个链表有n个分组可以反转，我们首先对第一个分组反转，那么接下来将剩余n-1个分组，n−1个分组反转后的结果接在第一组后面就行了，那这剩余的n−1组就是一个子问题。使用递归的三段式模版：
- 终止条件： 当进行到最后一个分组，即不足k次遍历到链表尾（0次也算），就将剩余的部分直接返回。
- 返回值： 每一级要返回的就是翻转后的这一分组的头，以及连接好它后面所有翻转好的分组链表。
- 本级任务： 对于每个子问题，先遍历k次，找到该组结尾在哪里，然后从这一组开头遍历到结尾，依次翻转，结尾就可以作为下一个分组的开头，而先前指向开头的元素已经跑到了这一分组的最后，可以用它来连接它后面的子问题，即后面分组的头。
具体做法：
- 步骤一：每次从进入函数的头节点优先遍历链表k次，分出一组，若是后续不足k个节点，不用反转直接返回头。
- 步骤二：从进入函数的头节点开始，依次反转接下来的一组链表，反转过程直接使用链表反转的算法。
- 步骤三：这一组经过反转后，原来的头变成了尾，后面接下一组的反转结果，下一组采用上述递归继续。
整个过程如图所示：
解题代码
Java版本实现
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// 1 定义分组尾节点
ListNode tail = head;
// 2 划分本级处理的区间反转子任务
for (int i = 0; i < k; i++) {
if (tail == null) {
// 2-1 任务停止条件是区间不足K个节点，此时直接返回这些节点即可
return head;
}
tail = tail.next;
}
// 3 处理本级区间反转任务
ListNode newHead = reverse(head, tail);
// 4 剩余区间继续递归反转，直到全部反转
head.next = reverseKGroup(tail, k);
return newHead;
}
private ListNode reverse(ListNode head, ListNode tail) {
ListNode pre = null;
ListNode cur = head;
while (cur != tail) {
ListNode pNext = cur.next;
cur.next = pre;
pre = cur;
cur = pNext;
}
return pre;
}
}
时间复杂度O(N)：遍历了一遍链表； 空间复杂度O(N/K)：递归最大的栈深度，
拓展：递归和迭代的区别
递归（Recursion）和迭代（Iteration）都是两种解决问题的方法，它们在实现方式和思维方式上有一些区别。
递归：
递归是一种通过将问题分解成更小的子问题来解决问题的方法。在递归中，函数会调用自身来解决子问题，直到达到基本情况（递归终止条件），然后逐层返回结果，最终得到整个问题的解。递归通常在问题的结构具有递归性质时使用，例如树形结构、链式结构等。
优点：
- 可以处理问题的复杂逻辑，将大问题分解为小问题。
- 在某些情况下，代码相对简洁易懂。
缺点：
- 递归可能会导致函数调用堆栈的增长，可能导致栈溢出。
- 递归的性能可能不如迭代。
递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度
为什么要求递归的深度呢？因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。
迭代：
迭代是通过循环控制来重复执行一系列操作，从而逐步逼近问题的解。在迭代中，通过在循环体内更新变量的值，逐步推进问题的求解，直到满足特定的条件为止。
优点：
- 迭代通常比递归更节省内存，因为不需要保存多层的函数调用信息。
- 性能更高，避免了函数调用的开销。
缺点：
- 在某些情况下，代码可能相对复杂，特别是涉及到复杂的循环控制逻辑。
在选择使用递归还是迭代时，需要考虑问题的性质、可读性、性能等因素。有些问题更适合用递归解决，而其他问题则更适合用迭代解决。有时候，递归和迭代也可以结合使用，例如一些动态规划问题。
