分析链表和递归问题

本篇内容主要讲解“分析链表和递归问题”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“分析链表和递归问题”吧!链表具有天然的递归性，一个链表可以看出头节点后面挂接一个更短的链表，这个更短的链表是以原链表的头节点的下一节点为头节点，依次内推，直到最后的更短的链表为空，空本身也是一个链表(最基础的)。以单链表 1->2->3->null 为例子，如下图示：原链表将原链表看出头节点 1 后挂接一个更短的链表头节点+更短链表继续拆解，直到无法拆解更更短链表更更更短链表有了这样的思考，很多「链表」相关问题，都可以采用「递归」的思路来解答。要反转链表，即将原链表的头节点变为新链表的尾节点，原链表的尾节点变为新链表的头节点。如下图示：反转之前：原链表反转之后：新链表主要策略主要有：1、直接修改链表的值，如上图中的原链表图所示，将原链表值 1 的头节点改为原链表尾节点的值，依次类推;2、让遍历整个链表，让链表的尾节点指向其前一个节点，依次类推。虽然这两个策略都可行，不过在面试中通常要求采用「策略2」。由上面的「递归与链表」可知，本题也可以采用「递归法」去求解。具体如何通过「递归」去解答呢?见下面例子。「举例」链表 1->2->3->null 为例子，如下图示。示例不断遍历找到原链表为尾节点，即新链表的头节点。原链表尾节点然后让尾节点指向其前驱节点，依次类推。递归反转详细步骤，如下动图示：递归反转单链表「C」「java」当然本题也可以采用「迭代」的方法去做，其代码(python 版)也很优雅，具体如下：「python」「复杂度分析」时间复杂度：「O(n)」，n 是链表的长度。对链表的每个节点都进行了反转操作。空间复杂度：「O(n)」，n 是链表的长度。递归调用的栈空间，最多为 n 层。要移除链表中给定值的节点，一般策略是「找到给点值的节点的前驱节点，然后让其指向给定值的节点的后继节点」。例如要删除链表 1->2->3->null 中，节点值为 3 的节点，就得先找到其前驱节点(值为 2 的节点)，如下图示：删除给定值的节点由上面的「递归与链表」可知，本题同样也可以采用「递归法」去求解，不断删除更短链表中给定值的节点，然后再将处理后的更短的链表，挂接在其前驱节点后。「注意」最后要判断原链表的头节点是否是待移除的节点。「举例」以链表 1->2->3->null 为例子，移除链表中给定值的节点的过程，如下动图示。示例动图「C++」「Golang」「复杂度分免费云主机、域名析」时间复杂度：「O(n)」，n 是链表的长度。递归需要遍历链表一次。空间复杂度：「O(n)」，n 是链表的长度。递归调用栈，最多不会超过 n 层。到此，相信大家对“分析链表和递归问题”有了更深的了解，不妨来实际操作一番吧！这里是云技术网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！

相关推荐: 怎么安装配置Docker

本篇内容主要讲解“怎么安装配置Docker”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“怎么安装配置Docker”吧!1. 介绍1.1 出现的原因前后端开发到测试到生产的过程中，经常会遇到一个问题，明明我在本地跑没…