LeetCode 面试题 02.06. 回文链表
文章目录
- 一、题目
- 二、C# 题解
一、题目
编写一个函数,检查输入的链表是否是回文的。
点击此处跳转题目。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
- 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
二、C# 题解
使用 O ( n ) O(n) O(n) 空间很容易写出来,只需要开辟一个数组或者反向链表即可。这里为了实现进阶要求,在原链表上修改。首先将链表的前半部分翻转,然后比较前后两个链表是否相同,最后恢复原链表即可,具体实现细节见代码注释:
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val = x; }* }*/
public class Solution {public bool IsPalindrome(ListNode head) {int n = 0, i;ListNode p = head, q;bool result;// 统计链表长度while (p != null) {p = p.next;n++;}if (n <= 1) return true; // 长度 <= 1,一定是回文串i = n / 2; // 长度的一半,向下取整p = head;while (--i > 0) p = p.next; // 定位到链表中间q = p.next;p.next = null; // 断开链表Reverse(head); // 翻转前半部分// 判断链表前后两部分是否相同if (n % 2 == 0) result = Same(p, q);else result = Same(p, q.next); // 奇数长度的链表需要跳过最中间的元素// 恢复链表原状Reverse(p);p.next = q;return result;}// 翻转链表public ListNode Reverse(ListNode head) {ListNode p = null, q = head, r;while (q != null) {r = q.next;q.next = p;p = q;q = r;}return p;}// 比较两个链表是否相同public bool Same(ListNode h1, ListNode h2) {while (h1 != null && h2 != null) {if (h1.val != h2.val) return false;h1 = h1.next;h2 = h2.next;}return h1 == null && h2 == null;}
}
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( 1 ) O(1) O(1)。
看了一下官方解法,发现还可以进行优化。使用快慢指针定位到中间节点,代码会更加高级和优雅hh。但是效率和上面统计长度然后遍历一半进行定位的方式差不多,因为都是遍历了一个半链表(快指针遍历整个链表,慢指针遍历半个链表),但是快慢指针这种方法它显得高级呀哈哈!
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val = x; }* }*/
public class Solution {public bool IsPalindrome(ListNode head) {if (head == null || head.next == null) return true;ListNode p = head, q = p.next; // p:慢指针,q:快指针bool result;while (q != null && q.next != null) {q = q.next.next; // q 前进两格if (q != null) p = p.next; // q 不为空,p 才前进}ListNode r = p.next; // 定位到后半段链表的首部p.next = null; // 断开链表Reverse(head); // 翻转前半部分// 判断链表前后两部分是否相同if (q != null) result = Same(p, r);else result = Same(p, r.next); // 奇数长度的链表需要跳过最中间的元素// 恢复链表原状Reverse(p);p.next = r;return result;}// 翻转链表public ListNode Reverse(ListNode head) {ListNode p = null, q = head, r;while (q != null) {r = q.next;q.next = p;p = q;q = r;}return p;}// 比较两个链表是否相同public bool Same(ListNode h1, ListNode h2) {while (h1 != null && h2 != null) {if (h1.val != h2.val) return false;h1 = h1.next;h2 = h2.next;}return h1 == null && h2 == null;}
}
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( 1 ) O(1) O(1)。
修改过后,发现快慢指针跑出来的速度不如直接统计链表长度来得快。果然,高端的代码往往以最朴素的方法写出来~
相关文章:
LeetCode 面试题 02.06. 回文链表
文章目录 一、题目二、C# 题解 一、题目 编写一个函数,检查输入的链表是否是回文的。 点击此处跳转题目。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true …...
linux环境没有curl或者telnet命令解决方法与区分linux环境类型
如何区分你当前使用的 Linux 系统是 Ubuntu、CentOS 还是 Alpine,查看 /etc/os-release 文件 [rootlocalhost ~]# cat /etc/os-release NAME"CentOS Linux" VERSION"7 (Core)" ID"centos" ID_LIKE"rhel fedora" VERSION_I…...
golang channel
channel是不同协程之间异步通信的数据结构。 基本用法 1 构造 ch:make(chan int)//无缓冲 ch:make(chan int,10)//有缓冲2 读操作 val:<-ch <-ch val,ok:<-ch3 写 var data int ch<-data4 关闭 close(ch)5 多路复用 select{ case <-parent.Done():child.…...
高等职业学校物联网实训室建设方案
一、概述 1.1专业背景 物联网(Internet of Things)被称为继计算机、互联网之后世界信息产业第三次浪潮,它并非一个全新的技术领域,而是现代信息技术发展到一定阶段后出现的一种聚合性应用与技术提升,是随着传感网、通…...
Python基础学习第四天:Python注释
创建注释 注释以 # 开头,Python 将忽略它们: 实例 #This is a comment print("Hello, World!")运行实例 注释可以放在一行的末尾,Python 将忽略该行的其余部分: 实例 print("Hello, World!")…...
Puppeteer中使用Stealth.min.js库
这里需要安装npm install puppeteer-extra puppeteer-extra-plugin-stealth,然后,在启动浏览器时,Puppeteer 会自动应用 Stealth.min.js 插件的功能。 const puppeteer require(puppeteer-extra); const StealthPlugin require(puppeteer-…...
JVM ZGC垃圾收集器
ZGC垃圾收集器 ZGC(“Z”并非什么专业名词的缩写,这款收集器的名字就叫作Z Garbage Collector)是一款在JDK 11中新加入的具有实验性质[1]的低延迟垃圾收集器,是由Oracle公司研发的。 ZGC收集器是一款基于Region内存布局的&#…...
事务管理-事务进阶-propagation属性
目录 事务属性-传播行为 propagation 案例 需求 步骤 具体代码 小结 事务属性-传播行为 propagation 事务传播行为:指的就是当一个事务方法被另一个事务方法调用时,这个事务方法应该如何进行事务控制。即如果事务方法A中调用了事务方法B,…...
树多选搜索查询,搜索后选中状态仍保留
<template><div class"half-transfer"><div class"el-transfer-panel"><div><el-checkbox v-model"selectAll" change"handleSelectAll">全部</el-checkbox></div><el-input v-model&qu…...
数据结构--字典树(trie)
概念: Trie 是一种能够快速插入和查询字符串的多叉树结构。、 节点的编号各不相同,根节点编号为0,其他节点用来标识路径,还可以标记单词的插入次数,边表示字符。 tire 维护字符串的集合,支持两种操作&…...
iframe通过postMessage进行跨域通信以及在Angular中使用
写在前面 在前端开发过程中,会遇到一些需要使用iframe的场景,使用iframe关键的一个点是数据之间的传输,基于同源的要求十分苛刻,大家基本上是都是跨域的,如果跨域进行数据传输呢? 大家使用的比较多的就是p…...
rust学习-引用C库
link和extern #[link(name = "...")] 是一个用于链接外部库的属性宏。 可以在 Rust 代码中引入其他语言编写的动态链接库(.so、.dll 等文件),从而实现 Rust 和其他语言的互操作。 #[link(name = "...")] 属性宏用于在 Rust 模块中引入标准 C 库(如 m…...
WebAssembly 在云原生中的实践指南
1 WebAssembly 介绍 WebAssembly(Wasm)是一种通用字节码技术,它可以将其他编程语言(如 Go、Rust、C/C 等)的程序代码编译为可在浏览器环境直接执行的字节码程序。 WebAssembly 的初衷之一是解决 JavaScript 的性能问…...
Azure sqlserver 更改字符集
前言 我们的Azure SQL Server是在2018年建的,当时还不支持汉字的字符集。然后最近发现因为字符集的缘故,出了bug,要调整字符集。然后就照着sqlserver 排序规则(字符集)查看与修改 一通修改。 然后神奇的事情来了&…...
git push时,由于commit了大文件无法成功push的解决办法
2句命令解决! 如图可以看见大文件的md5值,复制下来,以下命令会使用到 命令1: git rev-list --objects --all | grep b8d13387c0dfd7a8cec9ff0f6c8ded06eb21556f执行上面命令将得到,如下的输出,可以得知是…...
2023_Spark_实验一:Windows中基础环境安装
Ⅰ、WINDOWS中安装JDK1.8 一、下载安装包 链接:百度网盘 请输入提取码 所在文件夹:根目录或者大数据必备工具--》开发工具(前端后端)--》后端 下载文件名称:jdk-8u191-windows-x64.exe 二、安装JDK 1.现在转到下载的exe文件可用的文件夹&…...
如何在Windows / Mac / iPhone / Android / Online上将MP4转换为MP3
如果只想保留MP4视频的音频轨道,则可以将MP4转换为MP3格式。 MP3是几乎所有设备,播放器和编辑器都支持的数字音频格式。无论您将MP4视频转换为MP3音频以进行脱机播放或进一步编辑,都可以提取音轨并保存为MP3格式。这是在不损失质量的情况下将…...
【App端】uni-app使用百度地图api和echarts省市地图下钻
目录 前言方案一:echarts百度地图获取百度地图AK安装echarts和引入百度地图api完整使用代码 方案二:echarts地图和柱状图变形动画实现思路完整使用代码 方案三:中国地图和各省市地图下钻实现思路完整使用代码 前言 近期的app项目中想加一个功…...
深度学习(十)--- cv2.pointPolygonTest() 判断一点是否在指定区域内
今天发现了opencv一个好用的函数 cv2.pointPolygonTest() ,它可以判断一个点是否在指定区域内。 1. cv2.pointPolygonTest() 函数解析 dist cv2.pointPolygonTest(contour,point,Boolean)contour: 多边形轮廓 point: 坐标点 Boolean:True或False ,Tru…...
后端面试话术集锦第 八 篇:redis面试话术
这是后端面试集锦第八篇博文——redis面试话术❗❗❗ 1. 介绍一下redis Redis是一个非关系数据库,我们项目中主要用它来存储热点数据的,减轻数据库的压力,单线程纯内存操作,采用了非阻塞IO多路复用机制,就是单线程监听,我们项目中使用springdata-redis来操作redis。 我…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.
这个警告表明您在使用Vue的esm-bundler构建版本时,未明确定义编译时特性标志。以下是详细解释和解决方案: 问题原因: 该标志是Vue 3.4引入的编译时特性标志,用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...
循环语句之while
While语句包括一个循环条件和一段代码块,只要条件为真,就不断 循环执行代码块。 1 2 3 while (条件) { 语句 ; } var i 0; while (i < 100) {console.log(i 当前为: i); i i 1; } 下面的例子是一个无限循环,因…...
