当前位置: 首页 > news >正文

C# 回文链表

234 回文链表

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

示例 1:
在这里插入图片描述

输入:head = [1,2,2,1]
输出:true

示例 2:
在这里插入图片描述

输入:head = [1,2]
输出:false

提示:

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/palindrome-linked-list

解决方案:

提供思路

1) 最直观的方法是用数组存储链表中的每个结点的值,然后判断数组中的元素是否构成回文。遍历列表,将每个结点的值依次加入数组数字,此时数组中的元素顺序和链表的每个结点的值的顺序一致。

假设链表的结点数是大小,则数组数字的长度也是大小。数组数字中的元素构成回文,当且仅当对任意0≤我<大小都有数字[I]=数字[大小−1−我]。

2)为了将空间复杂度降低到O(1),不能使用数组存储链表的结点值,而是需要将链表的一半反转,然后比较链表的前后两半是否相同。

为了将链表的一半反转,需要首先找到链表的中间结点。可以使用「876. 链表的中间结点」的快慢指针的做法,使用O(1)空间找到链表的中间结点,当链表的结点数是偶数时,得到的是链表的第二个中间结点。快慢指针遍历结束时,快指针快移动到链表的尾结点或者空结点,慢指针慢移动到链表的中间结点。

链表的前一半为慢前面的部分,不包含慢,链表的后一半则由链表结点数的奇偶性决定:

·当链表的结点数是奇数时,链表的后一半从慢。下一个开始,此时链表的中间结点既不属于前一半也不属于后一半,其余每个结点都属于前一半或者后一半;

·当链表的结点数是偶数时,链表的后一半从慢开始,此时链表的每个结点都属于前一半或者后一半。

确定链表的前一半和后一半之后,将链表的前一半反转,即反转慢前面的部分,反转的部分不包含慢。反转链表的做法可以使用「206. 反转链表」的迭代解法,使得空间复杂度为O(1)。

上代码:

//1
public class Solution
{public bool IsPalindrome(ListNode head){IList<int> nums = new List<int>();ListNode node = head;while (node != null){nums.Add(node.val);node = node.next;}int size = nums.Count;for (int i = (size - 1) / 2; i >= 0; i--){int j = size - 1 - i;if (nums[i] != nums[j]){return false;}}return true;}
}//2
public class Solution
{public bool IsPalindrome(ListNode head){ListNode fast = head, slow = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}bool odd = fast != null;ListNode firstHalfEnd = slow;ListNode secondHalfStart = odd ? slow.next : slow;ListNode node1 = ReverseFirstHalf(head, firstHalfEnd);ListNode node2 = secondHalfStart;while (node1 != null){if (node1.val != node2.val){return false;}node1 = node1.next;node2 = node2.next;}return true;}public ListNode ReverseFirstHalf(ListNode head, ListNode firstHalfEnd){ListNode prev = null, curr = head;while (curr != firstHalfEnd){ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

以上是碰到的第二百三十四题,后续持续更新。感觉对你有帮助的小伙伴可以帮忙点个赞噢!
在这里插入图片描述

相关文章:

C# 回文链表

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

基于freertos的温湿度蓝牙系统

前言&#xff1a;本项目主要是基于freertos的小项目&#xff0c;目的是为了巩固近期学习的知识&#xff0c;功能较简单&#xff0c;可自行扩充。 一、项目基本架构 项目基本功能&#xff1a;通过STM32单片机的freertos操作系统&#xff0c;将温湿度数据显示在oled屏幕上&#…...

华为云CTS 使用场景

云审计服务 CTS 云审计服务&#xff08;Cloud Trace Service&#xff09;&#xff0c;帮助您监控并记录华为云账号的活动&#xff0c;包括通过控制台、API、开发者工具对云上产品和服务的访问和使用行为&#xff0c;提供对各种云资源操作记录的收集、存储和查询功能&#xff0…...

【css】nth-child选择器实现表格的斑马纹效果

nth-child() 选择器可以实现为所有偶数&#xff08;或奇数&#xff09;的表格行添加css样式&#xff0c;even&#xff1a;偶数&#xff0c;odd&#xff1a;奇数。 代码&#xff1a; <style> table {border-collapse: collapse;width: 100%; }th, td {text-align: cente…...

找视频素材就上这8个网站,免费可商用,马住了。

自媒体创作者&#xff0c;视频剪辑一定要知道这8个高质量视频素材网站&#xff0c;免费可商用&#xff0c;赶紧收藏&#xff01; 菜鸟图库 https://www.sucai999.com/video.html?vNTYxMjky 菜鸟图库网素材非常丰富&#xff0c;网站主要还是以设计类素材为主&#xff0c;高清视…...

Springboot部署ELK实战

Springboot部署ELK实战 1、部署docker、docker-compose环境安装docker安装docker-compose 2、搭建elk1、构建目录&&配置文件1、docker-compose.yml 文档2、Kibana.yml3、log-config.conf 2、添加es分词器插件3、启动 3、Springboot项目引入es、logStash配置1、引入依赖…...

【Leetcode】76.最小覆盖子串(困难)

一、题目 1、题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存…...

C++ 指针函数和函数指针

除了void类型的函数之外&#xff0c;函数在调用结束之后都要有返回值&#xff0c;指针也可以是函数的返回值。当一个函数的返回值是指针类型时&#xff0c;这个函数就是指针型函数。 使用指针型函数的最主要目的就是要在函数结束时把大量的数据从被调函数返回到主调函数中。而通…...

JAVA实现存在更新不存在插入与及多余的进行删除(三)

这个版本&#xff0c;主要是迭代重载了下save方法&#xff0c;不废话&#xff0c;直接上代码&#xff1a; /*** 保存数据&#xff0c;处理数据的增删改** param paramData 前台的参数* param dbData 后台的数据* param clazz 前后台参数对应的class* param beanName …...

iMX6ULL驱动开发 | OLED显示屏SPI驱动实现(SH1106,ssd1306)

周日业余时间太无聊&#xff0c;又不喜欢玩游戏&#xff0c;大家的兴趣爱好都是啥&#xff1f;我觉得敲代码也是一种兴趣爱好。正巧手边有一块儿0.96寸的OLED显示屏&#xff0c;一直在吃灰&#xff0c;何不把玩一把&#xff1f;于是说干就干&#xff0c;最后在我的imax6ul的lin…...

拥抱创新:用Kotlin开发高效Android应用

拥抱创新&#xff1a;用Kotlin开发高效Android应用 引言 在当今数字时代&#xff0c;移动应用已经成为人们生活中不可或缺的一部分。无论是社交媒体、电子商务还是健康管理&#xff0c;移动应用已经深刻地影响了我们的生活方式。随着移动设备的普及和功能的增强&#xff0c;A…...

Effective Java笔记(20)接口优于抽象类

Java提供了两种机制&#xff0c;可以用来定义允许多个实现的类型&#xff1a;接口和抽象类。自从Java 8为继承引入了缺省方法( default method)&#xff0c;这两种机制都允许为某些实例方法提供实现。主要的区别在于&#xff0c;为了实现由抽象类定义的类型&#xff0c;类必须成…...

react学习笔记——1. hello react

包含的包一共有4个&#xff0c;分别的作用如下&#xff1a; babel.min.js&#xff1a;可以进行ES6到ES5的语法转换&#xff1b;可以用于import&#xff1b;可以用于将jsx转换为js。注意&#xff0c;在开发的时候&#xff0c;这个转换&#xff08;jsx转换js&#xff09;不在线上…...

明明已经安装字体,但IDEA、CLION无法找到思源黑体/Source Hans Sans的问题解决

IDEA、CLION的Jetbrain系列软件不支持非TrueType的中文字体&#xff0c;而Adobe官方给出的字体却不是TrueType的&#xff0c;所以便会导致Jetbrain系软件无法找到已安装的中文字体&#xff0c;因此我们需要安装TrueType的字体 请在以下Github链接中下载&#xff1a; TrueType思…...

2023-08-03力扣今日四题

链接&#xff1a; 剑指 Offer 67. 把字符串转换成整数 题意&#xff1a; 按规则将字符串转换成整数&#xff0c;规则不详叙 解&#xff1a; 字符串处理 实际代码&#xff1a; #include<iostream> #include<cstring> #include<climits> using namespac…...

【学会动态规划】最佳买卖股票时机含冷冻期(15)

目录 动态规划怎么学&#xff1f; 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后&#xff1a; 动态规划怎么学&#xff1f; 学习一个算法没有捷径&#xff0c;更何况是学习动态规划&#xff0c; 跟我…...

随机RSI震荡指标公式(StochRSI),RSI和KDJ二合一

随机RSI震荡指标(StochRSI)是由图莎尔钱德和斯坦利克罗发明的一种摆动指标&#xff0c;结合了相对强弱指标&#xff08;RSI&#xff09;和随机指标&#xff08;KDJ&#xff09;的原理&#xff0c;目的是提高灵敏度&#xff0c;解决RSI难以达到超买超卖区的问题&#xff0c;以便…...

轻松搭建酒店小程序

酒店小程序的制作并不需要编程经验&#xff0c;只需要按照以下步骤进行操作&#xff0c;就能很快地搭建自己的小程序商城。 第一步&#xff0c;注册登录账号进入操作后台&#xff0c;找到并点击【商城】中的【去管理】进入商城的后台管理页面&#xff0c;然后再点击【小程序商城…...

算法通过村——Hash和队列问题解析

算法的备胎Hash和找靠山的队列 备胎Hash Hash&#xff0c;不管是算法&#xff0c;还是在工程中都会大量使用。很多复杂的算法问题都用Hash能够轻松解决&#xff0c;也正是如此&#xff0c;在算法例就显得没什么思维含量&#xff0c;所以Hash是应用里的扛把子&#xff0c;但在算…...

租赁类小程序定制开发|租赁管理系统源码|免押租赁系统开发

随着互联网的发展&#xff0c;小程序成为了一种重要的移动应用开发方式。租赁小程序作为其中的一种类型&#xff0c;可以为很多行业提供便利和创新。下面我们将介绍一些适合开发租赁小程序的行业。   房屋租赁行业&#xff1a;租房小程序可以帮助房东和租户快速找到合适的租赁…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...