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

Leetcode 04 java

坚持坚持坚持!!!!呵呵额呵呵不想学了,坚持坚持坚持坚持坚持!!!!

题目



234. 回文链表

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

示例 1:

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

示例 2:

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

提示:

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

进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

题解

class Solution {public boolean isPalindrome(ListNode head) {// 创建一个动态数组vals,用于存储链表中的所有节点值List<Integer> vals = new ArrayList<Integer>();// 将链表的值复制到数组中ListNode currentNode = head;  // 初始化当前节点为头节点while (currentNode != null) {  // 遍历链表直到末尾vals.add(currentNode.val);  // 将当前节点的值添加到数组中currentNode = currentNode.next;  // 移动到下一个节点}// 使用双指针法判断数组是否是回文结构int front = 0;  // 前指针初始化为数组的起始位置int back = vals.size() - 1;  // 后指针初始化为数组的末尾位置while (front < back) {  // 当两个指针还未相遇时// 如果前指针和后指针所指的元素不相等if (!vals.get(front).equals(vals.get(back))) {return false;  // 说明不是回文,返回false}front++;  // 前指针向后移动一位back--;   // 后指针向前移动一位}return true;  // 如果所有元素都匹配,则返回true}
}

通俗解释

这个程序是用来判断一个链表是否是回文链表的。回文链表的意思是,链表中的元素从前往后读和从后往前读是一样的,就像 "1221" 或者 "racecar" 这样的字符串。

程序的工作流程是这样的:

  1. 复制链表到数组:首先,程序会把链表中的每个数字按顺序放到一个动态数组里。这是因为链表不像数组那样可以直接从后往前访问,所以我们需要先把链表的值存到数组中。

  2. 双指针法检查回文:然后,程序使用两个指针,一个从前向后移动,另一个从后向前移动。每次比较这两个指针指向的数字是否相同:

    • 如果在任何时候发现两个指针指向的数字不一样,就说明这个链表不是回文链表,程序会立即返回false
    • 如果两个指针相遇了还没有发现不同的数字,就说明链表是回文链表,程序会返回true

进阶思考

这种方法的时间复杂度是 O (n),因为我们需要遍历链表一次,然后再遍历数组一次。空间复杂度也是 O (n),因为我们需要一个数组来存储链表的所有元素。

如果要达到 O (1) 的空间复杂度,我们可以:

  1. 找到链表的中间点
  2. 反转后半部分链表
  3. 比较前半部分和反转后的后半部分
  4. 恢复链表(可选)

但这些步骤会让代码变得更复杂,而当前提供的方法已经足够简单易懂了。

我觉得不是很难理解,就是自己写会写不出来,然后后面如果会反转链表的操作,这道题目还可以自己琢磨一下!

http://www.lryc.cn/news/592216.html

相关文章:

  • 今日行情明日机会——20250718
  • 【Spring WebFlux】什么是响应式编程
  • Linux入门篇学习——借助 U 盘或 TF 卡拷贝程序到开发板上
  • 证券行业 SCRM 落地:企业微信与系统协同的合规技术方案
  • 二进制写入与文本写入的本质区别:系统视角下的文件操作
  • 数据结构:顺序表和链表
  • 【PTA数据结构 | C语言版】我爱背单词
  • 【PTA数据结构 | C语言版】二叉堆的朴素建堆操作
  • HTML 页面禁止缩放功能
  • 深入解析文本分类技术全景:从特征提取到深度学习架构
  • 数据库的基础概操作
  • 计算机视觉与机器视觉
  • 基于物联网的智能农情监测预警系统
  • 深入解析PyQt5信号与槽的高级玩法:解锁GUI开发新姿势
  • Maven学习总结(62)—— Maven 打包瘦身和提速解决方案
  • 电网驱鸟黑科技:鸟类AI识别算法+无人机实现“智慧护线“
  • 在ajax中什么时候需要将返回值类型做转换
  • 【教程】基于无人机的大豆光合效率研究
  • 实战指南|智慧无人机安防系统搭建全流程解析
  • 前端项目利用Gitlab CI/CD流水线自动化打包、部署云服务
  • 无人机悬停技术运行与难点分析
  • 【QT】调用外部dll
  • 无人机传感器模组运行与技术难点分析
  • Python练习(5)Python参数传递的20道核心实战练习题(含答案与深度解析)(下)
  • H3CNE小小综合实验
  • js中的微任务和宏任务的理解
  • 【宇树科技:未来1-3年,机器人可流水线打螺丝】
  • 脚手架本地link标准流程
  • Java HashMap高频面试题深度解析
  • SpringBoot-27-企业云端开发实践之跨域认证JWT