首页 > 其他分享 >递归魔法

递归魔法

时间：2024-02-06 17:56:17浏览次数：26  
标签：head ListNode 递归 反转 魔法 next 链表 节点

反转单链表的迭代实现不是一个困难的事情，但是递归实现就有点难度了，如果再加一点难度，让你仅仅反转单链表中的一部分，你是否能够递归实现呢？

本文就来由浅入深，step by step 地解决这个问题。如果你还不会递归地反转单链表也没关系，本文会从递归反转整个单链表开始拓展，只要你明白单链表的结构，相信你能够有所收获。

// 单链表节点的结构体
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;

// 创建单链表节点的函数
ListNode* createNode(int x) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = x;
node->next = NULL;
return node;
}

// 释放单链表节点的函数
void freeNode(ListNode* node) {
free(node);
}

什么叫反转单链表的一部分呢，就是给你一个索引区间，让你把单链表中这部分元素反转，其他部分不变。

看下力扣第 92 题「反转链表 II」：

注意这里的索引是从 1 开始的。迭代的思路大概是：先用一个 for 循环找到第 m 个位置，然后再用一个 for 循环将 m 和 n 之间的元素反转。但是我们的递归解法不用一个 for 循环，纯递归实现反转。

迭代实现思路看起来虽然简单，但是细节问题很多的，反而不容易写对。相反，递归实现就很简洁优美，下面就由浅入深，先从反转整个单链表说起。

一、递归反转整个链表

这也是力扣第 206 题「反转链表」，递归反转单链表的算法可能很多读者都听说过，这里详细介绍一下，直接看代码实现：

#include <stdio.h>
#include <stdlib.h>

// 单链表节点的结构体
typedef struct ListNode {
int val;   // 节点的值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;

// 反转单链表的函数
ListNode* reverse(ListNode* head) {
// 如果链表为空或只有一个节点，直接返回链表头指针
if (head == NULL || head->next == NULL) {
return head;
}
// 递归地反转链表中除头节点以外的部分，并返回反转后的链表头指针
ListNode* last = reverse(head->next);

// 将当前头节点的下一个节点的 next 指针指向当前头节点，实现反转
head->next->next = head;

// 将当前头节点的 next 指针置为 NULL，断开与下一个节点的连接
head->next = NULL;

// 返回反转后的链表头指针
return last;
}

// 打印单链表的函数
void printList(ListNode* head) {
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}

int main() {
// 创建示例单链表: 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->val = 1;
head->next = (ListNode*)malloc(sizeof(ListNode));
head->next->val = 2;
head->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->val = 3;
head->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->val = 4;
head->next->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->next->val = 5;
head->next->next->next->next->next = NULL;

printf("Original list: ");
printList(head);

// 反转单链表
head = reverse(head);

printf("Reversed list: ");
printList(head);

// 释放单链表的内存
ListNode* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}

return 0;
}

看起来是不是感觉不知所云，完全不能理解这样为什么能够反转链表？这就对了，这个算法常常拿来显示递归的巧妙和优美，我们下面来详细解释一下这段代码。

对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverse 函数定义是这样的：

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

明白了函数的定义，再来看这个问题。比如说我们想反转这个链表：

那么输入 reverse(head) 后，会在这里进行递归：

 ListNode* last = reverse(head->next);

不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：

这个 reverse(head->next) 执行完成后，整个链表就成了这样：

并且根据函数定义，reverse 函数会返回反转之后的头结点，我们用变量 last 接收了。

现在再来看下面的代码：

head->next->next = head;

接下来：

head->next = NULL; 
return last;

神不神奇，这样整个链表就反转过来了！递归代码就是这么简洁优雅，不过其中有两个地方需要注意：

1、递归函数要有 base case，也就是这句：

if (head == NULL || head->next == NULL) {
return head;
}

意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。

2、当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：

head->next = NULL;

理解了这两点后，我们就可以进一步深入了，接下来的问题其实都是在这个算法上的扩展。

反转链表前 N 个节点

这次我们实现一个这样的函数：

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode* reverseN(ListNode* head, int n)

比如说对于下图链表，执行 reverseN(head, 3)：

解决思路和反转整个链表差不多，只要稍加修改即可：

#include <stdio.h>
#include <stdlib.h>

// 单链表节点的结构体
typedef struct ListNode {
int val;   // 节点的值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode* reverseN(ListNode* head, int n, ListNode** successor) {
if (n == 1) {
// 当 n 为 1 时，记录下 head->next，以便后续节点指向
*successor = head->next;
return head;
}
// 递归地反转以 head->next 为起点的 n-1 个节点
ListNode* last = reverseN(head->next, n - 1, successor);

// 将 head->next->next 指向 head，完成翻转
head->next->next = head;
// 将 head->next 指向 successor，与后面的节点连接
head->next = *successor;

return last;  // 返回新的头结点
}

// 打印单链表的函数
void printList(ListNode* head) {
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}

int main() {
// 创建示例单链表: 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->val = 1;
head->next = (ListNode*)malloc(sizeof(ListNode));
head->next->val = 2;
head->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->val = 3;
head->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->val = 4;
head->next->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->next->val = 5;
head->next->next->next->next->next = NULL;

printf("Original list: ");
printList(head);

int n = 3;  // 反转节点的个数
ListNode* successor = NULL;

// 反转以 head 为起点的 n 个节点
head = reverseN(head, n, &successor);

printf("Reversed list: ");
printList(head);

// 释放单链表的内存
ListNode* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}

return 0;
}

具体的区别

1、base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。

2、刚才我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

反转链表的一部分

现在解决我们最开始提出的问题，给一个索引区间 [m, n]（索引从 1 开始），仅仅反转区间中的链表元素。

ListNode* reverseBetween(ListNode* head, int m, int n)

首先，如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是我们刚才实现的功能：

如果 m != 1 怎么办？如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……

区别于迭代思想，这就是递归思想，所以我们可以完成代码：

#include <stdio.h>
#include <stdlib.h>

// 单链表节点的结构体
typedef struct ListNode {
int val;   // 节点的值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;

// 单链表节点反转
ListNode* reverseN(ListNode* head, int n, ListNode** successor) {
if (n == 1) {
// 当 n 为 1 时，记录下 head->next，以便后续节点指向
*successor = head->next;
return head;
}
// 递归地反转以 head->next 为起点的 n-1 个节点
ListNode* last = reverseN(head->next, n - 1, successor);

// 将 head->next->next 指向 head，完成翻转
head->next->next = head;
// 将 head->next 指向 successor，与后面的节点连接
head->next = *successor;

return last;  // 返回新的头结点
}

// 反转从第 m 个节点到第 n 个节点
ListNode* reverseBetween(ListNode* head, int m, int n) {
// base case
if (m == 1) {
ListNode* successor = NULL;
return reverseN(head, n, &successor);
}
// 前进到反转的起点触发 base case
head->next = reverseBetween(head->next, m - 1, n - 1);
return head;
}

// 打印单链表的函数
void printList(ListNode* head) {
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}

int main() {
// 创建示例单链表: 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->val = 1;
head->next = (ListNode*)malloc(sizeof(ListNode));
head->next->val = 2;
head->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->val = 3;
head->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->val = 4;
head->next->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->next->val = 5;
head->next->next->next->next->next = NULL;

printf("Original list: ");
printList(head);

int m = 2;  // 反转起点
int n = 4;  // 反转终点

// 反转从第 m 个节点到第 n 个节点
head = reverseBetween(head, m, n);

printf("Reversed list: ");
printList(head);

// 释放单链表的内存
ListNode* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}

return 0;
}

至此，我们的最终大 BOSS 就被解决了。

最后总结

递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。

处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。

值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。

标签：head,ListNode,递归,反转,魔法,next,链表,节点
From： https://www.cnblogs.com/lulixiu1999/p/18010114

相关文章

  • 递归
    递归A方法调用B方法，我们很容易理解！递归就是：A方法调用A方法！！就是自己调用自己！！利用递归可以用简单的程序来解决一些复杂的问题。它通常把一个大型复杂的问题层层转化为一个与原问题相似的的规模较小的问题来求解。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复......
  • 洛谷题单指南-递推与递归-P1464 Function
    原题链接：https://www.luogu.com.cn/problem/P1464题意解读：虽然a、b、c可输入的范围比较大，但是递归中，只会限制在0-20以内，由于递归中有大量的重复计算，因此需要采用记忆化搜索来保存已经计算过的递归函数值。解题思路：定义三位数组LLmem[25][25][25]，mem[a][b][c]保存w(a,b,c)的......
  • 【CPL-2023】W7笔记-递归
    递归数学归纳法：基础情况归纳步骤通过参数控制问题解决的规模传参不同可能会导致不同的递归深度有可能造成栈溢出递归中冗余的调度归并排序-递归版不能直接在待排序的数组上进行swap操作，因为会造成原有数据的覆盖后面复杂二分查找-递归版快速排序-递归版qui......
  • 【洛谷 P2437】蜜蜂路线 题解（递归+记忆化搜索+高精度）
    蜜蜂路线题目描述一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房开始爬到蜂房，，有多少种爬行路线？（备注：题面有误，右上角应为）输入格式输入的值输出格式爬行有多少种路线样例#1样例输入#1114样例输出#1377提示对于100%的......
  • 洛谷题单指南-递推与递归-P1028 [NOIP2001 普及组] 数的计算
    原题链接：https://www.luogu.com.cn/problem/P1028题意解读：给定n，构造数列，可以用递归或者递推。解题思路：1、递归定义count(n)返回数列的个数  n==1时，count(n)=1  n!=1时，count(n)=1+count(1)+count(2)+...+count(n/2)注意，递归会导致大量重复计算，需要用一个hash......
  • 洛谷题单指南-递推与递归-P1044 [NOIP2003 普及组] 栈
    原题链接：https://www.luogu.com.cn/problem/P1044题意解读：一组数入栈、出栈的方案数，如果了解卡特兰数，此题可以秒杀；如果不了解，也可以通过递归或者递推来解决；最次，可以通过DFS暴搜出方案数，当然对于n个数，一共有n次入栈、n次出栈，一共2n次，每次要么入栈要么出栈，总搜索次数在22n规模，n最......
  • Erlang 学习之第三天 . 函数,模块,递归,数字,字符串
    Erlang函数Erlang是一种众所周知的函数式编程语言，因此您将看到许多关于函数如何在Erlang中工作的重点。本章介绍如何使用Erlang中的函数完成所有操作。直接上实例:定义函数add(X,Y) ->    Z = X+Y,    io:fwrite("~w~n",[Z]). start() ->    add(5,6).......
  • 洛谷题单指南-递推与递归-P1002 [NOIP2002 普及组] 过河卒
    原题链接：https://www.luogu.com.cn/problem/P1002题意解读：从A（0,0）点走到B（n，m）点，只能向右或者向下，C点以及其控制点不能走。解题思路：根据题意，此题要么递归（DFS），要么递推（动态规划）先分析数据规模，最大从起点到终点要走40步，每个步有2种走法，一共240种路径，DFS会超时，且方案数必须用longlong......
  • 【洛谷 P2249】【深基13.例1】查找（向量+二分查找+递归）
    【深基13.例1】查找题目描述输入个不超过的单调不减的（就是后面的数字不小于前面的数字）非负整数，然后进行次询问。对于每次询问，给出一个整数，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出。输入格式第一行个整数和，表示数字个数和询问次数。第二行......
  • Shell 避免无限递归
    在编写Shell脚本时，有时会产生我们不期望的递归。比如说，我曾经写过一个脚本，名为foo.sh。foo.sh的内容如下：functionfoo{#TODO}foo然后我在.zshrc里设置了别名：aliasfoo="source~/foo.sh"现在，当我在终端运行foo时，就会得到如下错误：/Users/undefined443/foo......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99