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

判断回文链表【两种O(n)时间复杂度】

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:head = [1,2,2,1]
输出:true
示例 2:
输入:head = [1,2]
输出:false
LeetCode链接:https://leetcode.cn/problems/palindrome-linked-list

思路一、使用数组辅助存储

        链表的难点在于无法获取前一个元素,因此可以考虑将前半部分的元素使用数组进行存储,然后逆序和链表进行比较。基于以上思路,可以得到以下代码:

class Solution {
public:bool isPalindrome(ListNode* head) {int length = 0;ListNode* tmp = head;while(tmp){length++;tmp = tmp->next;}vector<int> halfList(length / 2);tmp = head;for (int i = 0; i < length / 2; i++) {halfList[i] = head->val;head = head->next;}if(1 == length%2){head = head->next;}for (int i = (length + 1) / 2; i < length; i++) {if (head->val != halfList[length - i -1])return false;head = head->next;}return true;}
};

执行结果:
Vector

思路二、使用栈和递归

        回文链表最重要的是判断两端是否相等,一段在头,一段在尾,这种方式完美适配队列和栈,因此可以将元素值分别压入队列和栈,然后进行判断。根据以上思路可以得到以下代码:

class Solution {
public:bool isPalindrome(ListNode* head) {stack<int> valStack;queue<int> valQueue;while (head) {valStack.push(head->val);valQueue.push(head->val);head = head->next;}while (!valStack.empty()) {if (valQueue.front() != valStack.top())return false;valQueue.pop();valStack.pop();}return true;}
};

执行结果:
Stack、Queue

关于代码执行时间的思考

        两种算法都是O(n)级别的时间复杂度,执行时间应该相仿,但是可以明显看出,使用队列和栈的方法明显慢于使用列表的方法,这可能是因为队列和栈中有大量的出入栈、出入队列操作,而且列表中使用了提前结束,但是队列和栈中则是进行了全部遍历。为此,在队列中加入长度计数器,提前终止减少出队列、出栈的操作次数。得到了以下改进后的思路二代码:

class Solution {
public:bool isPalindrome(ListNode* head) {int length = 0;stack<int> valStack;queue<int> valQueue;while (head) {valStack.push(head->val);valQueue.push(head->val);head = head->next;length++;}//改为使用长度进行判断for (int i = 0; i < length / 2; i++) {if (valQueue.front() != valStack.top())return false;valQueue.pop();valStack.pop();}return true;}
};

执行结果:
优化
可以看到,降低了近一半的执行用时,但和列表相比还是耗费了大量用时。

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

相关文章:

  • 10_opencv_分离颜色通道、多通道图像混合
  • Netty中trySuccess和setSuccess的区别
  • Java程序员学从0学AI(七)
  • mybatis-plus-tenant-support
  • Caddy服务器指南
  • 工业计算机的重要性
  • C# 提取字符串 指定开始和结尾字符
  • JAVA+AI教程-第四天
  • 2,智能制造,MOM,MES - 柔性制造(具体内容参考PPT文档)
  • 接口测试核心概念与实践指南
  • 分享一个脚本,从mysql导出数据csv到hdfs临时目录
  • 安装及使用vscode
  • 基于EKF的单站相位差变化率定位实现
  • 【论文阅读】Safety Alignment Should Be Made More Than Just a Few Tokens Deep
  • Solidity基础(教程①-简单数字存储)
  • AI项目实战:使用Python进行专业级数据集处理的完整教程
  • MySQL面试题及详细答案 155道(001-020)
  • 生产力效能跃升 金士顿DDR5 5600内存
  • JavaWeb 新手学习路线:从零到全栈开发,系统掌握企业级 Web 开发技能
  • 经典算法题解析:从思路到实现,掌握核心编程思维
  • 开发笔记 | 实现人物立绘的差分效果
  • 四、计算机组成原理——第5章:存储系统
  • 电子电路原理学习笔记---第4章二极管电路---第3天
  • 架构师增效指南:飞算JavaAI:需求驱动下的智能微服务拆分与治理
  • 浏览器安全演进:从裸指针到 raw_ptr 的实践与思考
  • leetcode 2044. 统计按位或能得到最大值的子集数目 中等
  • RV1126B-P机器视觉应用AIoT及边缘计算算力达2.0支持 HDR 、 3DNR
  • 网安学习NO.19
  • 构建 P2P 网络与分布式下载系统:从底层原理到安装和功能实现
  • SystemClock_Config 函数解析