【leetcode 刷题】19，linux 操作系统实用教程第二版

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

进阶：

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

Solution

相信大家都做过“回文”数字这道题，所谓回文就是正序和倒序遍历的结果是一样的。

那想想我们昨天做的题，正好是反转链表，所以我们就可以利用栈先进后出的特性先放进去，再拿出来比对，如果都相等，就是回文链表。

对于快慢双指针，其实也是利用翻转的思想，只不过是前半部分和后半部分比较。快慢指针的作用是找到中间的结点。慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

• 新建一个栈，记录两个等于 head 的链表，一个用来压入栈，一个用来出栈时的比较。

• 入栈

• 出栈比较

• 有不同的返回false
  

Code

所有leetcode代码已同步至github

欢迎star

/**

• @author yitiaoIT

*/

class Solution {

public boolean isPalindrome(ListNode head) {

Stack<Integer> 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)

??寻宝

《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享

?今天是坚持刷题更文的第 19/100 天

?各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力

?更多算法题欢迎关注专栏《leetcode》

最后

给大家送一个小福利

附高清脑图，高清知识点讲解教程，以及一些面试真题及答案解析。送给需要的提升技术、准备面试跳槽、自身职业规划迷茫的朋友们。

本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录