?欢迎订阅《leetcode》专栏,每日一题,每天进步?
一杯茶,一包烟,一道链表做一天
——leetcode此题热评
文章图片
前言 哈喽,大家好,我是一条。
糊涂算法,难得糊涂
周末肝了四篇文章,累趴了
Question 234. 回文链表 难度:简单
请判断一个链表是否为回文链表。Solution
示例 1:
输入: 1->2 输出: false
示例 2:
输入: 1->2->2->1 输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
相信大家都做过“回文”数字这道题,所谓回文就是正序和倒序遍历的结果是一样的。
那想想我们昨天做的题,正好是反转链表,所以我们就可以利用栈先进后出的特性先放进去,再拿出来比对,如果都相等,就是回文链表。
对于快慢双指针,其实也是利用翻转的思想,只不过是前半部分和后半部分比较。快慢指针的作用是找到中间的结点。慢指针一次走一步,快指针一次走两步,快慢指针同时出发。当快指针移动到链表的末尾时,慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
- 新建一个栈,记录两个等于head的链表,一个用来压入栈,一个用来出栈时的比较。
- 入栈
- 出栈比较
- 有不同的返回
false
所有leetcode
代码已同步至github
欢迎star
/**
* @author yitiaoIT
*/
class Solution {
public boolean isPalindrome(ListNode head) {
Stack stack = new Stack<>();
ListNode l1=head;
ListNode l2=head;
while (l1!=null){
stack.push(l1.val);
l1=l1.next;
}
while (!stack.isEmpty()){
if(stack.pop()!=l2.val){
return false;
}
l2=l2.next;
}
return true;
}
}
Result
复杂度分析
- 时间复杂度:O(N)
文章图片
寻宝
?今天是坚持刷题更文的第19/100天为了回馈各位粉丝,礼尚往来,给大家准备了一条多年积累下来的优质资源,包括 学习视频、面试资料、珍藏电子书等
?各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
?更多算法题欢迎关注专栏《leetcode》
怎么领取请大家自己找,寻宝游戏现在开始。
找不到可以评论留言,一条就会注意到你。
如果还不行,请私信我。
【算法练习300题|【leetcode刷题】19.回文链表——Java版】
文章图片
推荐阅读
- 数据结构|反转链表-四种方法
- 超级实习生|“进厂”第一课(大厂Java岗实习要求大盘点(内附2022/2023校招渠道整理))
- java面向对象学习|初学java(斐波那契数列的java实现)
- 全网最硬核 Java 新内存模型解析与实验 - 5. JVM 底层内存屏障源码分析
- 全网最硬核 Java 新内存模型解析与实验 - 4. Java 新内存访问方式与实验
- C语言|库函数《qsort》的模拟实现,原来如此简单
- c语言|(C语言)strstr库函数的简单使用以及模拟实现
- 全网最硬核 Java 新内存模型解析与实验 - 3. 硬核理解内存屏障(CPU+编译器)
- 全网最硬核 Java 新内存模型解析与实验 - 1. 什么是 Java 内存模型