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

蓝桥与力扣刷题(234 回文链表)

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

示例 1:

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

示例 2:

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

解题思路+代码:

代码:

/*** 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) {/**思路:1.判断链表是否为空或者单节点链表,为空直接返回true2.添加快慢指针,快指针一次走2步,慢指针一次走1步,即快指针的速度是慢指针的2倍(此时当快指针遍历到链表的最后,慢指针遍历到链表的中间)3.反转后半部分链表,与前半部分链表逐一匹配,一一对应返回true,否则返回false*/if (head == null || head.next == null){return true;}// 声明快慢指针ListNode fastNode = head;ListNode slowNode = head;// 遍历链表,慢指针找到链表中点while(fastNode != null && fastNode.next != null){slowNode = slowNode.next;fastNode = fastNode.next.next;}//反转慢指针后半部分链表与前半部分链表逐一匹配ListNode resversHalfList  = resversList(slowNode);ListNode P1 = head;ListNode p2 = resversHalfList;boolean res = true;while(p2 != null){if(P1.val != p2.val){res = false;break;}P1 = P1.next;p2 = p2.next;}// resversList(resversHalfList);return res;}private ListNode resversList(ListNode head){ListNode pre = null;ListNode cur = head;while(cur != null){ListNode nextTemp = cur.next;cur.next = pre;pre = cur;cur = nextTemp;}return pre;}}

总结:(错误思路:写这道题时我最初的思路是找到中间最大的数,然后依次向左右两边逐一遍历判断是否对称相等,一一对应为true,否则为false。)没错,上面的思路有很大的问题,且时间空间复杂度会相对复杂,因此我使用AI查询了我解题思路的错误所在。一:在回文链表当中,最大的数可能不止一个,此时的回文链表在找到最大的中间数依次向左右两侧依次遍历也可能会得到与预期相反的结果;二:通过指针向左右依次遍历判断不如快慢指针(上述代码有相应的解释如何找到链表的中点)找到中点后将前(后)链表部分反转,首先可判断前后部分的长度是否相等,不相等直接返回false,长度相等时则继续逐一匹配,直到确定是回文链表时返回true,使用快慢指针来遍历链表的时间和空间复杂度相对而言较简单,耗时较短。

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

相关文章:

  • Google C++ Style / 谷歌C++开源风格
  • Windows图形界面(GUI)-QT-C/C++ - QT Tab Widget
  • 【大数据技术】教程05:本机DataGrip远程连接虚拟机MySQL/Hive
  • C++:结构体和类
  • MATLAB的数据类型和各类数据类型转化示例
  • UE求职Demo开发日志#19 给物品找图标,实现装备增加属性,背包栏UI显示装备
  • C++泛型编程指南09 类模板实现和使用友元
  • 使用MATLAB进行雷达数据采集可视化
  • 【Elasticsearch】allow_no_indices
  • 54【ip+端口+根目录通信】
  • python算法和数据结构刷题[3]:哈希表、滑动窗口、双指针、回溯算法、贪心算法
  • DeepSeek横空出世,AI格局或将改写?
  • 聚簇索引、哈希索引、覆盖索引、索引分类、最左前缀原则、判断索引使用情况、索引失效条件、优化查询性能
  • OpenAI 实战进阶教程 - 第四节: 结合 Web 服务:构建 Flask API 网关
  • python的pre-commit库的使用
  • 架构技能(四):需求分析
  • Linux环境下的Java项目部署技巧:安装 Nginx
  • 前端 Vue 性能提升策略
  • 深入理解linux中的文件(上)
  • Unity特效插件GodFX
  • 从 C 到 C++:理解结构体中字符串的存储与操作
  • Linux进阶——时间服务器
  • 力扣 295. 数据流的中位数
  • 【Linux】进程状态和优先级
  • 携程Java开发面试题及参考答案 (200道-上)
  • Docker 部署教程jenkins
  • 深入理解开放寻址法中的三种探测序列
  • 图像噪声处理技术:让图像更清晰的艺术
  • linux运行级别
  • 深入剖析Electron的原理