432,剑指 Offer

Stella981
• 阅读 533

432,剑指 Offer

Success is stumbling from failure to failure with no loss of enthusiasm.

成功是在失败中摸索,同时不失去热情。

问题描述

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

限制:

0 <= 节点个数 <= 5000

使用栈解决

链表的反转是老生常谈的一个问题了,同时也是面试中常考的一道题。最简单的一种方式就是使用,因为栈是先进后出的。实现原理就是把链表节点一个个入栈,当全部入栈完之后再一个个出栈,出栈的时候在把出栈的结点串成一个新的链表。原理如下

432,剑指 Offer

代码比较简单,来看下

 1public ListNode reverseList(ListNode head) { 2    Stack<ListNode> stack = new Stack<>(); 3    //把链表节点全部摘掉放到栈中 4    while (head != null) { 5        stack.push(head); 6        head = head.next; 7    } 8    if (stack.isEmpty()) 9        return null;10    ListNode node = stack.pop();11    ListNode dummy = node;12    //栈中的结点全部出栈,然后重新连成一个新的链表13    while (!stack.isEmpty()) {14        ListNode tempNode = stack.pop();15        node.next = tempNode;16        node = node.next;17    }18    //最后一个结点就是反转前的头结点,一定要让他的next19    //等于空,否则会构成环20    node.next = null;21    return dummy;22}

双链表求解

双链表求解是把原链表的结点一个个摘掉,每次摘掉的链表都让他成为新的链表的头结点,然后更新新链表。下面以链表1→2→3→4为例画个图来看下。

432,剑指 Offer

432,剑指 Offer

他每次访问的原链表节点都会成为新链表的头结点,最后再来看下代码

 1public ListNode reverseList(ListNode head) { 2    //新链表 3    ListNode newHead = null; 4    while (head != null) { 5        //先保存访问的节点的下一个节点,保存起来 6        //留着下一步访问的 7        ListNode temp = head.next; 8        //每次访问的原链表节点都会成为新链表的头结点, 9        //其实就是把新链表挂到访问的原链表节点的10        //后面就行了11        head.next = newHead;12        //更新新链表13        newHead = head;14        //重新赋值,继续访问15        head = temp;16    }17    //返回新链表18    return newHead;19}

递归解决

我们再来回顾一下递归的模板,终止条件,递归调用,逻辑处理。

 1public ListNode reverseList(参数0) { 2    if (终止条件) 3        return; 4 5    逻辑处理(可能有,也可能没有,具体问题具体分析) 6 7    //递归调用 8    ListNode reverse = reverseList(参数1); 910    逻辑处理(可能有,也可能没有,具体问题具体分析)11}

终止条件就是链表为空,或者是链表没有尾结点的时候,直接返回

if (head == null || head.next == null)

递归调用是要从当前节点的下一个结点开始递归。逻辑处理这块是要把当前节点挂到递归之后的链表的末尾,看下代码

 1public ListNode reverseList(ListNode head) { 2    //终止条件 3    if (head == null || head.next == null) 4        return head; 5    //保存当前节点的下一个结点 6    ListNode next = head.next; 7    //从当前节点的下一个结点开始递归调用 8    ListNode reverse = reverseList(next); 9    //reverse是反转之后的链表,因为函数reverseList10    // 表示的是对链表的反转,所以反转完之后next肯定11    // 是链表reverse的尾结点,然后我们再把当前节点12    //head挂到next节点的后面就完成了链表的反转。13    next.next = head;14    //这里head相当于变成了尾结点,尾结点都是为空的,15    //否则会构成环16    head.next = null;17    return reverse;18}

因为递归调用之后head.next节点就会成为reverse节点的尾结点,我们可以直接让head.next.next = head;,这样代码会更简洁一些,看下代码

1public ListNode reverseList(ListNode head) {2    if (head == null || head.next == null)3        return head;4    ListNode reverse = reverseList(head.next);5    head.next.next = head;6    head.next = null;7    return reverse;8}

这种递归往下传递的时候基本上没有逻辑处理,当往回反弹的时候才开始处理,也就是从链表的尾端往前开始处理的。我们还可以再来改一下,在链表递归的时候从前往后处理,处理完之后直接返回递归的结果,这就是所谓的尾递归,这种运行效率要比上一种好很多

 1public ListNode reverseList(ListNode head) { 2    return reverseListInt(head, null); 3} 4 5private ListNode reverseListInt(ListNode head, ListNode newHead) { 6    if (head == null) 7        return newHead; 8    ListNode next = head.next; 9    head.next = newHead;10    return reverseListInt(next, head);11}

尾递归虽然也会不停的压栈,但由于最后返回的是递归函数的值,所以在返回的时候都会一次性出栈,不会一个个出栈这么慢。但如果我们再来改一下,像下面代码这样又会一个个出栈了

 1public ListNode reverseList(ListNode head) { 2    return reverseListInt(head, null); 3} 4 5private ListNode reverseListInt(ListNode head, ListNode newHead) { 6    if (head == null) 7        return newHead; 8    ListNode next = head.next; 9    head.next = newHead;10    ListNode node = reverseListInt(next, head);11    return node;12}

总结

链表反转使用栈虽然也能实现,但一般不是很推荐,下面两种实现方式会好一些。使用栈能实现链表的反转,那么使用队列呢,如果使用双端队列也是可以的,从一端全部入队,然后再从这一端全部出队,说了半天这不还是和栈一样吗……

432,剑指 Offer

431,剑指 Offer-链表中倒数第k个节点

429,剑指 Offer-删除链表的节点

410,剑指 Offer-从尾到头打印链表

352,数据结构-2,链表

432,剑指 Offer

长按上图,识别图中二维码之后即可关注。

如果觉得有用就点个"赞"吧

本文分享自微信公众号 - 数据结构和算法(sjjghsf)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Stella981 Stella981
3年前
Github标星5300+,专门为程序员开发文档开源管理系统,我粉了
!(https://oscimg.oschina.net/oscnet/a11909a041dac65b1a36b2ae8b9bcc5c432.jpg)码农那点事儿关注我们,一起学习进步!(https://oscimg.oschina.net/oscnet/f4cce1b7389cb00baaab228e455da78d0
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这