leetcode刷题之回文链表

目录

做题思路

代码实现

1.找到链表的中间节点

2.反转中间节点之后的链表

3.判断倒置的后半部分的链表是否等于前半部分的链表

整体代码展示

总结:



这里是题目链接。

 这道题目的意思是:判断该链表中后半部分倒置是否跟前半部分相同,如果相同就返回true,否则就返回false。

做题思路

1.先用快慢指针来找到该链表的中间节点。

2.倒置后半部分的链表。

3.判断倒置的部分是否跟前半部分相同。

代码实现

1.找到链表的中间节点

使用一个慢指针slow,一次走一步,一个快指针fast,一次走两步。当快指针fast为null或者走到尾节点时,slow所在的节点就是该链表的中间节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class solution{
    public boolean isPalindrome(ListNode head) {
        if(head == null) {
            return false;  //判断head是否为空
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时的slow就是链表的中间节点

我们在找到了中间节点后,接下来需要做的就是反转中间节点以后的链表

2.反转中间节点之后的链表

ListNode cur = slow.next;
while(cur != null) {
    ListNode nextNode = cur.next;    //nextNode用来记录cur的下一个节点
    cur.next = slow;  //将cur指向cur的前一个节点
    slow = cur;
    cur = nextNode;
}
//此时slow的位置就是在链表的尾节点处

3.判断倒置的后半部分的链表是否等于前半部分的链表

当链表的节点数为奇数时

当链表的节点数为偶数时

在执行这一步的时候我们需要注意:当链表的节点数为偶数跟奇数的时候,我们需要做出不同的判断来看前半部分的链表跟后半部分的链表是否走完了。

我们假设前半部分是从head1开始走的,后半部分的链表是从head2开始走的。当链表的节点数为奇数的时候,当head1跟head2相遇的时候就说明判断结束了。当链表的节点数为偶数的时候,当

head1.next = head2的时候,我们就可以说判断结束了。

ListNode head1 = head;
ListNode head2 = slow;
while(head1 != head2) {
    if(head1.val != head2.val) {
        return false;
    }
    if(head1.next == head2) {
        return true;
    }
    head1 = head1.next;
    head2 = head2.next;
}
return true;

整体代码展示

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode nextNode = cur.next;
            cur.next = slow;
            slow = cur;
            cur = nextNode;
            }
        while(head != slow ){
            if(head.val != slow.val) {
                return false;
            }
            if(head.next == slow) return true;
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

总结:

所以这道题你学会了吗?感谢大家的观看,以后也会更新关于C语言跟Java相关的知识,关注不迷路哦!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/1289.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

java 每日一练 (8)

文章目录1. 单选题2. 编程题1. 单选题 1. 下列选项中关于 java 中 super 关键字的说法正确的是 () A: super 关键字是在子类对象内部指代父类对象的引用. B : super 关键字不仅可以指代子类的直接父类,还可以直接指代父类的父类. C &#…

API-Server的监听器Controller的List分页失效

前言 最近做项目,还是K8S的插件监听器(理论上插件都是通过API-server通信),官方的不同写法居然都能出现争议,争议点就是对API-Server的请求的耗时,说是会影响API-Server。实际上通过源码分析两着有差别&am…

<script>标签在html中书写位置-课后程序(JavaScript前端开发案例教程-黑马程序员编著-第1章-课后作业)

【案例1-1】 <script>标签在html中书写位置 一、案例描述 考核知识点 <script>标签可以放在html中什么位置 练习目标 掌握<script>标签放在页面中不同位置的区别。 需求分析 将JavaScript标识放置<Head>... </Head>在头部之间&#xff0c;使之…

LInux指令之文件目录类

文章目录一、帮助指令二、文件目录类ls指令cd指令 &#xff08;切换目录&#xff09;mkdir指令&#xff08;创建目录&#xff09;rmdir指令&#xff08;删除目录&#xff09;touch指令&#xff08;创建空文件&#xff09;cp指令(拷贝文件)rm指令mv指令cat指令(查看)more指令les…

GEE:计算1990-2021年的指数最大值和最小值,并根据最大最小值对每一副影像归一化

本文记录了在GEE平台上计算影像集合中所有像素的最大值和最小值。并且根据该最大最小值对所有影像进行最大最小值归一化。以SAVI为例,记录了主要函数的使用方法和代码。 结果如图所示, 文章目录 一、计算每一副影像的最大值或者最小值,并将最值保存在 List 中二、计算 Lis…

AD域安全攻防实践(附攻防矩阵图)

以域控为基础架构&#xff0c;通过域控实现对用户和计算机资源的统一管理&#xff0c;带来便利的同时也成为了最受攻击者重点攻击的集权系统。 01、攻击篇 针对域控的攻击技术&#xff0c;在Windows通用攻击技术的基础上自成一套技术体系&#xff0c;将AD域攻防分为信息收集、权…

安装Docker

Docker分为CE和EE两大版本。CE即社区版&#xff08;免费&#xff0c;支持周期7个月&#xff09;&#xff0c;EE即企业版&#xff0c;强调安全&#xff0c;付费使用&#xff0c;支持周期 24 个月。 Docker CE 分为 stable test 和 nightly 三个更新频道。 官方网站上有各种环境…

Nacos 注册中心 - 健康检查机制源码

目录 1. 健康检查介绍 2. 客户端健康检查 2.1 临时实例的健康检查 2.2 永久实例的健康检查 3. 服务端健康检查 3.1 临时实例的健康检查 3.2 永久实例服务端健康检查 1. 健康检查介绍 当一个服务实例注册到 Nacos 中后&#xff0c;其他服务就可以从 Nacos 中查询出该服务…

LeetCode234_234. 回文链表

LeetCode234_234. 回文链表 一、描述 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&…

Day920.结构化日志业务审计日志 -SpringBoot与K8s云原生微服务实践

结构化日志&业务审计日志 Hi&#xff0c;我是阿昌&#xff0c;今天学习记录的是关于结构化日志&业务审计日志的内容。 1、什么是结构化日志 结构化日志&#xff08;Structured Logging&#xff09;是一种将日志信息组织为结构化数据的技术。 传统的日志通常是一些文…

UE实现建筑分层抽屉展示效果

文章目录 1.实现目标2.实现过程2.1 基础设置2.2 核心函数3.参考资料1.实现目标 使用时间轴对建筑楼层的位置偏移进行控制,实现分层抽屉的动画展示效果。 2.实现过程 建筑抽屉的实现原理比较简单,即对Actor的位置进行偏移,计算并更新其世界位置即可。这里还是基于ArchVizExp…

Mybatis报BindingException:Invalid bound statement (not found)异常

一、前言 本文的mybatis是与springboot整合时出现的异常&#xff0c;若使用的不是基于springboot&#xff0c;解决思路也大体一样的。 二、从整合mybatis的三个步骤排查问题 但在这之前&#xff0c;我们先要知道整合mybatis的三个重要的工作&#xff0c;如此才能排查&#x…

SDG,ADAM,LookAhead,Lion等优化器的对比介绍

本文将介绍了最先进的深度学习优化方法&#xff0c;帮助神经网络训练得更快&#xff0c;表现得更好。有很多个不同形式的优化器&#xff0c;这里我们只找最基础、最常用、最有效和最新的来介绍。 优化器 首先&#xff0c;让我们定义优化。当我们训练我们的模型以使其表现更好…

MySQL中事务的相关问题

事务 一、事务的概述&#xff1a; 1、事务处理&#xff08;事务操作&#xff09;&#xff1a;保证所有事务都作为一个工作单元来执行&#xff0c;即使出现了故障&#xff0c;都不能改变这种执行方式。当在一个事务中执行多个操作时&#xff0c;要么所有的事务都被提交(commit…

[ROC-RK3568-PC] [Firefly-Android] 10min带你了解Camera的使用

&#x1f347; 博主主页&#xff1a; 【Systemcall小酒屋】&#x1f347; 博主追寻&#xff1a;热衷于用简单的案例讲述复杂的技术&#xff0c;“假传万卷书&#xff0c;真传一案例”&#xff0c;这是林群院士说过的一句话&#xff0c;另外“成就是最好的老师”&#xff0c;技术…

再也不想去字节跳动面试了,6年测开面试遭到这样打击.....

前几天我朋友跟我吐苦水&#xff0c;这波面试又把他打击到了&#xff0c;做了快6年软件测试员。。。为了进大厂&#xff0c;也花了很多时间和精力在面试准备上&#xff0c;也刷了很多题。但题刷多了之后有点怀疑人生&#xff0c;不知道刷的这些题在之后的工作中能不能用到&…

【Python/Opencv】图像权重加法函数:cv2.addWeighted()详解

【Python/Opencv】图像权重加法函数&#xff1a;cv2.addWeighted()详解 文章目录【Python/Opencv】图像权重加法函数&#xff1a;cv2.addWeighted()详解1. 介绍2. API3. 代码示例与效果3.1 代码3.2 效果4. 参考1. 介绍 在OpenCV图像加法cv2.add函数详解详细介绍了图像的加法运…

字符串匹配【BF、KMP算法】

文章目录:star:BF算法代码实现BF的改进思路:star:KMP算法&#x1f6a9;next数组&#x1f6a9;代码实现优化next数组最终代码⭐️BF算法 BF算法&#xff0c;即暴力(Brute Force)算法&#xff0c;是普通的模式匹配算法&#xff0c;BF算法的思想就是将主串S的第一个字符与模式串P…

三、Python 操作 MongoDB ----非 ODM

文章目录一、连接器的安装和配置二、新增文档三、查询文档四、更新文档五、删除文档一、连接器的安装和配置 pymongo&#xff1a; MongoDB 官方提供的 Python 工具包。官方文档&#xff1a; https://pymongo.readthedocs.io/en/stable/ pip安装&#xff0c;命令如下&#xff1…

JVM调优,调的是什么?目的是什么?

文章目录前言一、jvm是如何运行代码的&#xff1f;二、jvm的内存模型1 整体内存模型结构图2 堆中的年代区域划分3 对象在内存模型中是如何流转的?4 什么是FULL GC,STW? 为什么会发生FULL GC?5 要调优,首先要知道有哪些垃圾收集器及哪些算法6 调优不是盲目的,要有依据,几款内…