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。 我…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
