LeetCode 206:反转链表 Reverse Linked List
反转一个单链表。
Reverse a singly linked list.
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
解题思路:
每次遍历到最后一位取节点这种方法就算了时间复杂度太高。如题目进阶要求的两种方法,迭代和递归:
迭代:
每次分出来一个节点把节点作为头节点添加到新链表上:
原链表:1->2->3->4->5
分离第一个节点作为头节点添加到新链表:1 原链表:2->3->4->5
分离下一个节点作为头节点添加到新链表:2->1 原链表:3->4->5
分离下一个节点作为头节点添加到新链表:3->2->1 原链表:4->5
分离下一个节点作为头节点添加到新链表:4->3->2->1 原链表:5
分离下一个节点作为头节点添加到新链表:5->4->3->2->1 原链表:null
Java:
class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode pre = null; ListNode tmp = null; while (head != null) { tmp = head.next;//tmp暂存当前节点的下一个节点 head.next = pre;//当前节点下一个指向pre pre = head;//刷新pre head = tmp;//刷新当前节点为tmp } return pre; } }
Python3:
class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head pre,tmp=None,None while(head): tmp=head.next head.next=pre pre=head head=tmp return pre
递归:
其实就是用递归完成栈的功能:先进后出
基线条件为遇到空节点(到链表末尾),返回对象为链表的最后一个节点,在递归函数中传递一直不变。从链表末尾向头部逐个分离节点,并将节点添加到新链表的末尾。与迭代法原理相似。
原链表:1->2->3->4->5
递归到最后一层时遇到null节点返回尾节点5
回到上一层递归 分离节点 5 作为新链表的尾节点:5,置空原本5节点,原链表1->2->3->4->null
回到上一层递归 分离节点 4 作为新链表的尾节点:5->4,置空原本4节点,原链表1->2->3->null
回到上一层递归 分离节点 3 作为新链表的尾节点:5->4->3,置空原本3节点,原链表1->2->null
回到上一层递归 分离节点 2 作为新链表的尾节点:5->4->3->2,置空原本2节点,原链表1->null
回到上一层递归 分离节点 1 作为新链表的尾节点:5->4->3->2->1,置空原本1节点,原链表null
Java:
class Solution { public ListNode reverseList(ListNode head) { //基线条件 if (head == null || head.next == null) return head; //递归 ListNode tmp = head.next;//暂存头节点的下一个节点 ListNode pre = reverseList(head.next);//递归调用该函数,pre为返回的新链表的头节点,原链表的最后一个节点,无论递归多少层该返回值一直传递不变 tmp.next = head;//暂存的下一个节点指向传入节点 head.next = null;//下一个节点即原本指向tmp的节点 置空 return pre; } }
Python3:
class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head tmp = head.next pre = self.reverseList(head.next) tmp.next = head head.next = None return pre
欢迎关注公.众号一起刷题:爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Lodash 严重安全漏洞背后 你不得不知道的 JavaScript 知识
摘要: 详解原型污染。 原文:Lodash 严重安全漏洞背后 你不得不知道的 JavaScript 知识 作者:Lucas HC Fundebug经授权转载,版权归原作者所有。 可能有信息敏感的同学已经了解到:Lodash 库爆出严重安全漏洞,波及 400万+ 项目。这个漏洞使得 lodash “连夜”发版以解决潜在问题,并强烈建议开发者升级版本。 我们在忙着“看热闹”或者“”升级版本”的同时,静下心来想:真的有理解这个漏洞产生的原因,明白漏洞修复背后的原理了吗? 这篇短文将从原理层面分析这一事件,相信“小白”读者会有所收获。 漏洞原因 其实漏洞很简单,举一个例子:lodash 中 defaultsDeep 方法, _.defaultsDeep({ 'a': { 'b': 2 } }, { 'a': { 'b': 1, 'c': 3 } }) 输出: { 'a': { 'b': 2, 'c': 3 } } 如上例,该方法: 分配来源对象(该方法的第二个参数)的可枚举属性到目标对象(该方法的第一个参数)所有解析为 undefined 的属性上 这样的操作存在的隐患: const payl...
- 下一篇
Fundebug:JavaScript插件支持错误采样
Fundebug的付费套餐主要是根据错误事件数制定的,这是因为每一个发送到我们服务器的事件,都会消耗一定的CPU、内存、磁盘以及带宽资源,尤其当错误事件数非常大时,会对我们的计算资源造成很大压力。 如果您希望采样收集错误,比如“只收集30%的错误”,可以将sampleRate属性设为0.3。这样的话,您可以选择更加合适套餐。 1. 在HTML中配置<script>标签中配置sampleRate属性 <script src="https://js.fundebug.cn/fundebug.1.9.0.min.js" apikey="API-KEY" sampleRate=0.3></script> 2. 在JavaScript中配置sampleRate变量 fundebug.sampleRate = 0.3; 注意,是否收集错误是完全随机的,因此理论上这样可能会导致一些错误不会被收集。因此,您需要自行权衡利弊,选择是否配置sampleRate以及配置多大的sampleRate。 参考 Fundebug计费标准解释:事件数是如何定义的? 版权声明 转载时...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8编译安装MySQL8.0.19
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2全家桶,快速入门学习开发网站教程