本章我们将使用递归方式反向打印一个链表;注意并不是反转链表，而是反向打印。...之前我们说明过递归的写法 1.列出两数关系公式 2.找出退出条件 要遍历必然有x=x->link; 退出条件是当link=NULL ，相信对你聪明的你来说这很容易理解。...递归代码 void Print(Node*x) { if (x==NULL) { return; } Print(x->link); printf...(" %d ", x->data); } 他的函数执行流程大致是这样 通过内存视图看一下: 由于先执行了递归，在满足返回条件时，递归将不再继续，再执行完Print(50)之后，再执行打印链表的操作...，这样链表就被反转打印了。
bug如下图： 困扰了我好长时间，在老师和同学的帮助下，终于解决了。原因是字段名没有对应 改成和数据库字段名一样即可，并将实体类的相关方法重新编写即可
有迭代（双指针）、递归两种实现方法。 方法一：迭代（双指针） 考虑遍历链表，并在访问各节点时修改 next 引用指向，算法流程见注释。...复杂度分析： 时间复杂度 O(N)： 遍历链表使用线性大小时间。 空间复杂度 O(1)： 变量 pre 和 cur 使用常数大小额外空间。...考虑使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。...传入 null 是因为反转链表后， head 节点指向 null ； 复杂度分析： 时间复杂度 O(N)) ： 遍历链表使用线性大小时间。...空间复杂度 O(N)： 遍历链表的递归深度达到 N ，系统使用 O(N)大小额外空间。
辅助空间： O(1) 使用递归反转链表： 这个想法是使用递归到达链表的最后一个节点，然后开始反转链表。 插图： 请按照以下步骤解决问题： 将链表分为两部分——第一个节点和链表的其余部分。...将头指针修复为 NULL 下面是上述方法的实现: """使用递归方法反转链接表的 Python3 程序 使用递归方法""" # 链接列表节点 class Node: def __init__(self...、current和next，递归访问每个节点并使用这三个指针建立链接。...，则只需从当前节点到前一个节点进行反向链接并更新头。 ...辅助空间： O(N)，函数调用栈空间 使用Stack反转链表： 这个想法是将所有节点存储在堆栈中，然后创建一个反向链表。 请按照以下步骤解决问题： 将节点（值和地址）存储在堆栈中，直到输入所有值。
ListNode* l = new ListNode(0); input(l); Solution s; bool ret=s.isPalindrome(l); cout << "链表打印...return 0; } 方法二：递归 使用递归反向迭代节点，同时使用递归函数外的变量向前迭代 class Solution { ListNode* frontPointer;...public: //该函数用来对链表进行递归和回溯比较的操作 bool recursivelyCheck(ListNode* head) { /...=NULL) { //这条If语句的作用： //1.不断进行递归，进行递归的过程中还没有进行判断...=NULL,返回true，此时回退到尾节点 //(2):从尾节点进行回退的过程中，如果出现不匹配，就表示该链表不是回文链表，便会一直满足该if语句条件，返回false，直到回溯结束
下面是程序锅自己对网上发布的 200 道高频面试题进行分类之后的结果。这 200 道，程序锅大概花了 7 个月刷完了，并且差不多每道题都过了好几遍。...-删除排序链表中的重复元素（基本操作）-1 offer06-从尾到头打印链表（基本操作）-1 206-反转链表（双指针、递归）-1 92-反转链表2（双指针、递归）-2 24-两两交换链表中的节点（双指针...（queue） offer32-二叉树的层序遍历/从上到下打印二叉树 2（queue） offer32-二叉树的锯齿形层次遍历/从上到下打印二叉树 3（queue） 114-二叉树展开为链表（莫里斯遍历...） 230-二叉搜索树中第 K 小的元素（类似与第 K 大的元素） 109-有序链表转换二叉搜索树（递归+快慢指针、中序遍历框架） 98-验证二叉搜索树（中序遍历的结果、递归的方式） offer33-...（两种递归：自底而上，自顶而下） offer28/101-对称的二叉树（一种递归、一种迭代）/对称二叉树 617-合并二叉树（递归） 98-验证二叉搜索树（中序遍历的结果、递归的方式） 堆 题目 313
示例： 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 解法一：迭代（双指针） 在线链接 本方法是对链表进行遍历，然后在访问各节点时修改 next 的指向...cur.next = pre; // 将当前节点指向反向链表，这是一个建立反向链接的过程 pre = cur; // 更新反向链表的头指针为当前已处理的节点，反向链表的该轮构建完成 cur...= temp; // 将正向链表头指针替换为暂存的节点，正向链表处理完成，开始下一轮处理 } return pre; }; 复杂度分析 时间复杂度 O(N)：遍历链表使用线性大小时间。...解法二：递归 在线链接 当使用递归对链表进行处理时，从链表的第一个节点出发，然后找到最后一个节点，该节点就是反转链表的头结点，然后进行回溯处理。 初始链表的头结点，head 标识。...，需要对链表的每个节点进行反转操作。
限制： 思路及代码 这道题的关键在于如何执行替换操作，如果我们使用常规的从前往后遍历字符串替换空格，由于需要将 1 个字符替换为 3 个字符，因此替换时需要将当前字符后面的所有字符整体后移，这会导致总的时间复杂度达到...面试题 6：从尾到头打印链表 ❝题目：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。...，栈弹出相当于反向遍历一遍链表，「空间复杂度」为 ，因为额外使用了一个栈来存储链表中的每个节点。...python 可以使用 list 和其切片特性实现栈的操作。 除了栈，我们还可以使用「递归」来解决上述问题，因为递归本质上就是一个栈结构。...每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点自身，这样链表的输出结果就反过来了。
一般地，递归问题都能转换为循环进行求解。 1.4递归举例 1.4.1 字符串反向输出 描述：输入字符串abc，要求能输出cba，以此类推。...0时，就是递归出口。...当n=1或n=2时，可以直接获取结果，因此可以作为递归的出口；而fn(n-1) = fn(n-2)+fn(n-3),我们看到，该问题再向出口一步步靠近，也就是问题规模在不断减小，因此满足递归的条件。...分析：对于阶乘，我们同样可以使用递归求解。我们令fn(n)=!n,那么fn(n-1)=(n-1)!,从而fn(n)=nfn(n-1),当n=1时，那么fn(1)=10!...=1,能够直接获得的结果可以作为递归出口，同时，我们看到阶乘的规模在一步步减小，直到直接获得作为递归出口的结果。代码如下所示。
2、使用一个简单的案例，数组求和，使用递归算法进行计算。案例，如下所示： 1 package com.array; 2 3 /** 4 * 数组求和，使用递归算法进行计算。...递归函数的调用，本质就是函数调用，和普通函数的调用没有区别，只不过调用的函数是自己而已。 5.1、数组求和，使用递归算法进行计算。递归调用的函数微观解读。 ?...5.2、使用链表递归解决，删除链表中等于给定值val的所有节点，微观层面的步骤解析。 ?...6、递归算法的调试，可以根据打印输出或者开发工具的debug进行调试即可。...7、关于递归，链表具有天然的递归结构，近乎和链表相关的所有操作，都可以使用递归的形式来完成，比如，可以使用递归对链表进行增加，删除，修改和查询操作的。 7.1、双链表的结构。 ?
题目： 输入一个链表的头结点，从尾到头反过来打印出每个结点的值。...this.val = val; } } 思路： 从尾到头，我们首先想到的就是栈这个结构，栈是先进先出的结构，先进来的元素最后再出去，所以本题我们可以考虑用栈来解决 想到栈的同时我们也应该联想到递归...代码： 1 import java.util.Stack; 2 3 import org.junit.jupiter.api.Test; 4 5 /** 6 * 反向打印链表...stack.empty()) { 30 System.out.println(stack.pop().key); 31 } 32 } 33 34 //采用递归...System.out.println("采用栈："); 58 printListRever(ListNode1); 59 System.out.println("采用递归
题目描述 输入一个链表，从尾到头打印链表每个节点的值。...题目描述 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则 分析 我们使用其中的一个结点将两个链表拼接起来，换句话说，就是将一个链表合并到另一个链表上，所以并不能创建一个新链表去进行操作...这个过程是重复的，所以我们这里可以使用递归操作，反之，当l2的结点小于l1时，就把l1拼接到l2上 class Solution: # 返回ListNode def ReverseList...题目描述 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则 分析 我们使用其中的一个结点将两个链表拼接起来，换句话说，就是将一个链表合并到另一个链表上，所以并不能创建一个新链表去进行操作...分析 首先对特殊边界条件进行判断，然后分别递归左右子树，向下递归时需要使用目标值减去根节点的值，最后将左右子树的递归结果拼接为一个列表进行遍历，使用一个新列表去接受根节点加上遍历的元素值 class Solution
阈值时(16)，使用直接插入排序处理 当元素个数超过__stl_threshold时，考虑是否能用快排的方式排序，因为当元素数量达到一定程度，递归式的快排可能会导致栈溢出而崩，因此： 通过__lg函数判断递归的深度...2* 时，则使用快排方式排序，注意：快排时使用到了三数取中法预防分割后一边没有数据的极端情况 如果递归深度超过2* 时，说明数据量大，递归层次太深，可能会导致栈溢出，此时使用堆排序处理。...list底层结构为带头结点的双向循环链表，迭代器在移动时，只能按照链表的结构前后依次移动，因此链表的迭代器需要对原生态的指针进行封装，因为当对迭代器++时，应该通过节点中的next指针域找到 下一个节点...如果迭代器不能直接使用原生态指针操作底层数据时，必须要对指针进行封装，在封装时需要提供以下方法： 迭代器能够像指针一样方式进行使用：重载 pointer operator*() / reference...反向迭代器++和–操作刚好和正向迭代器相反，因此：反向迭代器只需将正向迭代器进行重新封装即可。
题目： 输入一个链表，要求从尾到头打印该链表，链表结点定义如下： struct ListNode { int value; ListNode *next; }; 解题思路： 要求很好理解...打印的结果是：6 5 4 3 2 1 1.相信大多数人看到这个要求后的第一反应是反转链表，再从头打印，但是这样一来，原始数据就改变了。...4.既然想到了是一种“先遍历后打印，后遍历先打印”的操作，那么可不可以不借助栈来实现这个方法——递归。...递归的思想在合并两个排序的链表题目中就使用过，只不过在该题目中我们返回的是最后一次递归的结果，而在本文的题目我们需要打印每一次递归的返回值。...关于思路3和4都是可以的，具体使用哪一个可以根据实际情况来决定，如果链表很长，那么递归调用的层数就会很深，可能导致函数调用栈溢出，用思路3的鲁棒性会更好一些。
4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基 本上均摊结果就等于低级别复杂度。...2.均摊时间复杂度 两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别 复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。...经常用来检查链表代码是否正确的边界条件有这样几个： 如果链表为空时，代码是否能正常工作？ 如果链表只包含一个结点时，代码是否能正常工作？ 如果链表只包含两个结点时，代码是否能正常工作？...归并排序使用的就是分治思想。分治算法一般都是用递归来实现的。（分治是一种解决问题的处理思想，递归是一种编程技巧） * 归并排序是一个稳定的排序算法。...使用循环和递归都可以实现二分查找。 二分查找应用场景的局限性： * 二分查找依赖的是顺序表结构，简单点说就是数组。（链表不可以） * 二分查找针对的是有序数据。（如果数据没有序，我们需要先排序。）
二叉树其实是链表的升级版，即链表同时拥有两个 Next 指针，就变成了二叉树。...说完了反向，我们说正向，即递归一颗二叉树。 其实二叉树除了递归，还有一种常见的遍历方法是利用栈进行广度优先遍历，典型题目有从上到下打印二叉树。...这道题要求从左到右顺序打印，完全遵循广度优先遍历，我们可以在二叉树递归时，先不要急着读取值，而是按照左、中、右，遇到左右子树节点，就推入栈的末尾，利用 while 语句不断循环，直到栈空为止。...利用展开时追加到栈尾，并不断循环处理栈元素的方式非常优雅，而且符合栈的特性。 当然如果题目要求倒序打印，你就可以以 右、中、左 的顺序进行处理。 接下来看看深度优先遍历，典型题目是二叉树的深度。...有一道二叉树的题目，是根据树的深度，按照广度优先遍历打印成二维数组，记录树的深度其实也有巧妙办法，即在栈尾追加元素时，增加一个深度 key，那么访问时自然就可以读到深度值。
从尾到头打印链表」 力扣题目链接[1] 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。...解析：我们先正序遍历链表，同时将链表的值存入数组中。直到链表为空则停止遍历。最后将数组进行倒置后返回，则是最终结果。...总结 暴力法和辅助栈法的区别是一个使用数组的 API 进行元素倒置，一个使用辅助栈进行元素倒置。面试中应该尽量使用辅助栈的思路进行题解，暴力法不能体现出栈的特点。 「剑指 Offer 24....临时变量也在交换变量时进行使用，此处同理。核心思路就是先暂存当前节点的next 指向，然后改变next指向为pre，然后将pre和cur后移一位。...递归 本题也可以使用递归进行处理，通过回溯来修改next指向。 使用递归进行解题，一定要写递归的终止条件，否则会造成死循环导致内存溢出。
(List* pl); //实现逆序打印的递归函数 void reverse_travel(Node* pn); //清空链表中所有的节点 void clear(List* pl); int main...reverse_data(&list); travel(&list);// 44 22 88 printf("--------------------------\n"); printf("逆序打印的结果是...："); reverse_travel_data(&list);// 88 22 44 printf("正序打印的结果是："); travel(&list);// 44 22 88 printf...= pop_head(pl)); } //逆序打印链表中的所有节点元素 void reverse_travel_data(List* pl) { //1.调用递归函数进行打印 reverse_travel...= NULL) { //1.打印后续节点元素值，使用递归 reverse_travel(pn->next); //2.打印头节点元素值 printf("%d ",pn->data);
这是我参与「掘金日新计划 · 10 月更文挑战」的第13天，点击查看活动详情 递归 在算法刷题中，往往会使用到递归方法解题，虽然递归将一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，...，递归会对此再次进行计算。...优化思路：将子问题的计算结果保存，同一子问题可直接调取使用。...n的元素 递推式：F(n) = 打印F(n) + F(n-1) 终止条件： if (n<0) return; 递归代码就可以这样写： void solution(int[] nums) { print...时，退出递归。
在遍历链表的时候，当快指针遍历完成时，慢指针刚好达到中点。 对于第三个问题 设置两个指针，其中一个指针先移动k个节点。之后两个指针以相同速度移动。...与递归有关的一些优化 （1）.对于可以递归的问题考虑状态保存 当我们使用递归来解决一个问题的时候，容易产生重复去算同一个子问题，这个时候我们要考虑状态保存以防止重复计算。...例如用hashMap来进行保存，当然用一个数组也是可以的，这个时候就像我们上面说的巧用数组下标了。可以当arr[n] = 0时，表示n还没计算过，当arr[n] !...不过，有时候当n比较大的时候，例如当 n = 10000时，那么必须要往下递归10000层直到 n <=2 才将结果慢慢返回，如果n太大的话，可能栈空间会不够用。...总结一下 当你在使用递归解决问题的时候，要考虑以下两个问题 (1). 是否有状态重复计算的，可不可以使用备忘录法来优化。 (2). 是否可以采取递推的方法来自底向上做，减少一味递归的开销。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
