反转链表 Java版 图文并茂思路分析带答案(力扣第206题)

这篇具有很好参考价值的文章主要介绍了反转链表 Java版 图文并茂思路分析带答案(力扣第206题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

反转链表

力扣第206题

我们不只是简单的学习(背诵)一个数据结构,而是要分析他的思路,以及为什么要有不同的指针等等

非递归方式:

思路分析:首先要链表有个头指针没有任何问题

然后,我们要将1的下一个节点指向空,这样才能将其反转过来,但是这个时候我们发现和下一个节点2失去了联系

所以我们要有一个指针,在1还没有将next指向空前,记录下2的位置。所以我们用一个next指针记录2。并为了好理解,将head改名为cur代表当前节点。

因此,我们只要将cur的指向下一个节点的指针指向空之后,便将cur和next指针同时向后移动。

不过这样我们发现,我们cur和前面的节点失去了联系,就不能将节点2指向1了,所以我们还要有一个指针负责记录前一个节点,我们就叫它pre吧,那么再来考虑pre指针最开始应该放在哪呢,其实只要指向最左边的那个NULL就好了。

因此我们刚刚是将1指向NULL,现在改成将cur指向pre即可,就像这样。

然后我们就可以将这三个指针都向后移动,重复上一步和本步操作,直到cur为null结束即可。

递归方式:

首先是写出递归的最后答案,也就是所谓的递归出口,毫无疑问是返回第一个节点head

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

再调用一次递归函数

reverseListRecursive(head.next);

直接从宏观的角度上看,肯定是将head.next之后的所有节点都反转过来了,就像下图所示,其中1被挡住了不要在意。

重点来了,如何将最后的节点2指向节点1,并将节点1指向空?

其实用两行代码实现即可,将head.next(节点2).next(NULL)指向节点1,也就是 = head即可

然后再将节点1指向空,也即head.next = null;

 head.next.next = head;
 head.next = null;

力扣答案总结:

我们来具体实现一下吧,其中的reverseList内的代码即是力扣答案文章来源地址https://www.toymoban.com/news/detail-449664.html

/**
 * @Author: 翰林猿
 * @Description: 反转链表
 **/
public class ReverseListNode {
    //非递归方式
    public ListNode reverseList(ListNode head) {
        //初始化三个指针,其中latter要在过程中指定,因为有可能cur为空,导致latter为空
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode latter = cur.next;
            //将cur指向pre
            cur.next = pre;
            //三个指针都向后移动,其中pre和cur在这里移动,latter在第一句会自行移动。
            pre = cur;
            cur = latter;
        }
        return pre;
    }
    //递归方式
    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next==null)
            return head;
        ListNode rev = reverseListRecursive(head.next);     //最后会获取到head
        head.next.next = head;
        head.next = null;
        return rev;
    }
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
​
        ListNode node = new ReverseListNode().reverseList(head);
        System.out.println("反转后的第一个节点值应当为5 = "+node.val);
​
        ListNode node2 = new ReverseListNode().reverseListRecursive(head);
        System.out.println("递归反转后的第一个节点值应当为5 = "+node.val);
    }
}
​
​
class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

到了这里,关于反转链表 Java版 图文并茂思路分析带答案(力扣第206题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java 线程池详解,图文并茂,还有谁不会?!

    来源:blog.csdn.net/mu_wind/article/details/113806680 我们知道,线程的创建和销毁都需要映射到操作系统,因此其代价是比较高昂的。出于避免频繁创建、销毁线程以及方便线程管理的需要,线程池应运而生。 降低资源消耗 :线程池通常会维护一些线程(数量为 corePoolSize),这些线

    2024年02月06日
    浏览(53)
  • Java中抽象类和接口的区别,一文弄懂,图文并茂

    前言 1. 抽象类 1.1 定义 1.2 示例 1.3 使用 1.3.1代码-抽象类 1.3.2代码-抽象类继承类使用 1.3.3输出结果为: 1.4UML类图展示类间的关系 2. 接口 2.1 定义 2.2 示例 2.2.1代码-接口 2.3 使用 2.3.1代码-接口实现 2.3.2代码-接口实现类使用 2.3.3输出结果为: 2.4UML类图展示类间的关系 3. 抽象类和

    2024年02月04日
    浏览(46)
  • Activiti7(图文并茂)

    Activiti 是由 jBPM (BPM,Business Process Management 即业务流程管理) 的创建者 Tom Baeyens 离开 JBoss 之后建立的项目,构建在开发 jBPM 版本 1 到 4 时积累的多年经验的基础之上,旨在创建下一代的 BPM 解 决方案。 Activiti 作为一个开源的工作流引擎,它实现了BPMN 2.0规范,可以发布设计

    2024年02月06日
    浏览(55)
  • secureCRT安装和使用教程【图文并茂】

    简介 一般而言,嵌入式开发板使用串口来监控后台。可以使用串口线连接开发板和电脑,对于没有串口的笔记本电脑来说,一般还需要一根USB转串口线。 串口线 串口软件多种多样,比如secureCRT、Xshell、超级终端、miniCom、putty等,它们的功能大同小异,因此只需安装用的顺手

    2024年02月03日
    浏览(89)
  • RabbitMQ入门篇【图文并茂,超级详细】

    接下来看看由辉辉所写的关于RabbitMQ的相关操作吧 目录 🥳🥳Welcome 的Huihui\\\'s Code World ! !🥳🥳 前言 1.什么是MQ 2.理解MQ 3.生活案例分析与理解 4.MQ的使用场景 (1)解耦 传统模式 中间件模式 (2)削峰 传统模式 中间件模式 (3)异步  传统模式 中间件模式 5.常见的MQ 一. Rab

    2024年01月20日
    浏览(48)
  • 发送图文并茂的html格式的邮件

    本文介绍如何生成和发送包含图表和表格的邮件,涉及echarts图表转换为图片、图片内嵌到html邮件内容中、html邮件内容生成、邮件发送方法等 因为html格式的邮件不支持echarts,也不支持js执行,所以图表需要转换为图片内嵌在邮件内容中 因为平台首页相关统计都是使用echarts渲

    2024年02月11日
    浏览(37)
  • NodeMCU ESP8266开发流程详解(图文并茂)

    NodeMCU ESP8266基于Arduino IDE的开发相对来说还是比较容易上手的,我们基本需要以下几个东西; 一台安装好Arduino IDE的PC,并且已经部署环境(安装好开发板的串口驱动); NodeMCU ESP8266 开发板; USB线(根据实际开发板的情况,本文需要Micro-USB的线); 具体如下图所示; 本文默

    2024年02月06日
    浏览(54)
  • 什么是感知机——图文并茂,由浅入深

    生活中常常伴随着各种各样的逻辑判断,比如看到远方天空中飘来乌云,打开手机看到天气预报说1小时后40%的概率下雨,此时时候我们常常会做出等会下雨,出门带伞的判断。 上述思考过程可以抽象为一个”与“的”神经逻辑“。当”看到乌云“和”天气预报40%下雨“同时

    2023年04月20日
    浏览(38)
  • Flutter 图文并茂:打造交互丰富的应用界面

    Flutter作为一种现代的UI工具包,为开发者提供了丰富的工具和小部件,轻松构建漂亮、响应迅速的应用界面。本篇博客将带你踏入Flutter的世界,学习如何巧妙运用图片、按钮、图标,以及行与列进行布局,打造令人惊艳的用户交互体验。 无论你是Flutter初学者还是有一定经验

    2024年02月03日
    浏览(39)
  • 总线仿真与测试工具CANoe介绍(图文并茂)

    CANoe是德国Vector公司的一款用于开发、测试和分析单个ECU和整个ECU网络的综合性工具,包括 软件 和 硬件 。它在整个开发过程中为网络设计者、开发和测试工程师提供支持:从规划到系统级测试。由于其多种变体和功能能够对不同的项目提供支持,被全球OEM和供应商广泛使用

    2024年02月01日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包