从今天开始进行高频算法的训练，一方面训练自己的逻辑思维，一方面保持自己的竞争力。训练过程有这么两个基准原则：

• 首先训练题的来源呢有三个，首选的是三个都出现过的高频题，以：牛客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 如果为空列表，返回nullif (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的下一个位置

步骤主要分为两大步骤

1. pre和cur同时向后走m步到达要反转的列表区间，pre指向反转区间前一个节点，cur为当前反转子区间的头节点
2. 进行n-m次的节点反转，每次反转目标都是将pNext移动到pre的后边，分三步

这三个步骤是：

1. cur.next = pNext.next;: cur指向下一个待转节点
2. pNext.next=pre.next: pNext节点指向反转子区间的尾节点，成为反转子区间新的尾节点
3. 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指向反转子区间新的尾节点pNextpre.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）都是两种解决问题的方法，它们在实现方式和思维方式上有一些区别。

递归：
递归是一种通过将问题分解成更小的子问题来解决问题的方法。在递归中，函数会调用自身来解决子问题，直到达到基本情况（递归终止条件），然后逐层返回结果，最终得到整个问题的解。递归通常在问题的结构具有递归性质时使用，例如树形结构、链式结构等。

优点：

• 可以处理问题的复杂逻辑，将大问题分解为小问题。
• 在某些情况下，代码相对简洁易懂。

缺点：

• 递归可能会导致函数调用堆栈的增长，可能导致栈溢出。
• 递归的性能可能不如迭代。

递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

为什么要求递归的深度呢？因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

迭代：
迭代是通过循环控制来重复执行一系列操作，从而逐步逼近问题的解。在迭代中，通过在循环体内更新变量的值，逐步推进问题的求解，直到满足特定的条件为止。

优点：

• 迭代通常比递归更节省内存，因为不需要保存多层的函数调用信息。
• 性能更高，避免了函数调用的开销。

缺点：

• 在某些情况下，代码可能相对复杂，特别是涉及到复杂的循环控制逻辑。

在选择使用递归还是迭代时，需要考虑问题的性质、可读性、性能等因素。有些问题更适合用递归解决，而其他问题则更适合用迭代解决。有时候，递归和迭代也可以结合使用，例如一些动态规划问题。