算法—回文链表

news/2024/12/24 13:08:35/

题目链接:https://leetcode.cn/problems/palindrome-linked-list/description/

题目

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

示例1:

示例1图片

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

输出:true

示例2:

示例2图片

输入:head = [1,2]

输出:false

思路

有两种思路解决这个问题:

  1. 使用一个数据结构:栈。先进后出,遍历链表依次存到栈中,再从栈中弹出节点和链表的值比较;
  2. 反转后半段链表,双指针,一个从前往后,一个从后往前,依次比较。

其中方法一,可以扩展一下,其实只用比较前一半和后一半值就好,所以栈中只需要存放一半的的链表就好。

两个思路得出三种方法,其中用栈的方法做题的速度就比较快,不需要扣边界条件,而用反转链表双指针的方法就需要扣出边界,优点是用的额外空间少。

方法一:栈存全链表

这个方法就比较无脑了,一股脑存,再一股脑弹出:

  1. 先遍历所有节点,每个节点都压进栈
  2. 再从头节点开始,每个节点和弹出栈的值比较
  3. 有一个不一样的,就直接返回 false
  4. 所有节点遍历结束,返回 true

示意图

方法1

代码

class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}Stack<Integer> s = new Stack();ListNode temp = head;// 压栈while (temp != null) {s.push(temp.val);temp = temp.next;}// 弹出比较while (head != null) {if (head.val != s.pop()) {return false;}head = head.next;}return true;}
}

方法二:栈存一半链表

和第一个方法的思路一样,只是压栈的时候只压链表的后一半节点,再弹出比较。只不过需要多考虑一点边界条件。

示意图

方法2

代码

class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 找到中点的下一个位置ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}slow = slow.next;// 后半段链表压栈Stack<Integer> s = new Stack<>();while (slow != null) {s.push(slow.val);slow = slow.next;}// 链表不为 null,就弹出比较while (!s.isEmpty()) {if (head.val != s.pop()) {return false;}head = head.next;}return true;}
}

方法三:反转链表

先反转后半段链表,一个指针从前往后走,一个指针从后往前走,每次都比较一下,只要有一次不一样,就直接返回 false,全部比较完,返回 true

示意图

方法3

代码

class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 反转后半段链表ListNode n1 = head;ListNode n2 = head;while (n2.next != null && n2.next.next != null) {n1 = n1.next;n2 = n2.next.next;}ListNode n3 = null;while (n1 != null) {n2 = n1.next;n1.next = n3;n3 = n1;n1 = n2;}// 判断是否回文n1 = head;while (n1 != null) {if (n1.val != n3.val) {return false;}n1 = n1.next;n3 = n3.next;}return true;}
}

总结

这是一道 LeetCode 简单题,适合新手锻炼寻找链表相关的边界条件,思路不难,代码实现起来也比较容易。

Tips:你能用第三种方法使用完之后将链表恢复吗?快来试试吧!


http://www.ppmy.cn/news/1557743.html

相关文章

富格林:曝光交易良方阻挠损失

富格林悉知&#xff0c;投资者在出金环节受到阻挠时&#xff0c;要注意多留几个心眼避免损失。因为据曝光黄金市场的活跃表现可以为投资者创造了许多获利机会&#xff0c;但是想要通过炒黄金赚钱&#xff0c;就必须掌握一些有效的交易技巧。以下富格林总结曝光几点做单的技巧&a…

Java 实现日志文件大小限制及管理——以 Python Logging 为启示

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。运营社区&#xff1a;C站/掘金/腾讯云/阿里云/华为云/51CTO&#xff1b;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互…

LiteFlow决策系统的策略模式,顺序、最坏、投票、权重

个人博客&#xff1a;无奈何杨&#xff08;wnhyang&#xff09; 个人语雀&#xff1a;wnhyang 共享语雀&#xff1a;在线知识共享 Github&#xff1a;wnhyang - Overview 想必大家都有听过或做过职业和性格测试吧&#xff0c;尤其是现在的毕业生&#xff0c;在投了简历之后经…

C# OpenCV机器视觉:角度和方向检测

又是一个无聊的周末&#xff0c;阿强正准备享受他期待已久的休闲时光。他打算去公园散步&#xff0c;拍几张美丽的风景照&#xff0c;顺便享受一下大自然的气息。正当他兴致勃勃地走出家门&#xff0c;脑海中幻想着与阳光、花朵和微风的亲密接触时&#xff0c;手机突然响了起来…

如何在电脑上控制手机?

在现代生活中&#xff0c;通过电脑控制手机已经成为一种高效的工作和娱乐方式。Total Control 是一款实用的电脑端软件&#xff0c;通过USB或Wi-Fi连接&#xff0c;用户可以在电脑上直接操作多台手机,通过电脑键盘输入文字&#xff0c;提高操作效率。特别适合需要大屏操作的用户…

如何判断产品需不需要做ATT认证?ATT测试内容和要求分享

随着经济全球化的发展&#xff0c;国内越来越多产品厂商选择将自家产品出口到北美市场&#xff0c;而这时候各位厂商都会面临产品需不需要做AT&T的问题。今天英利检测针对这一问题整理了一些关于AT&T认证中的测试内容与测试要求&#xff0c;供大家参考。 AT&T认证的…

使用 Vite 和 Redux Toolkit 创建 React 项目

文章目录 1. 创建 React 项目2. 安装依赖3. 创建状态仓库user.js创建 shopSlice 4. 在状态仓库中合并切片5. 在入口文件中导入并使用 store6. 获取切片中的数据7. 修改数据结尾 在本教程中&#xff0c;我们将通过使用 Vite 创建一个 React 项目&#xff0c;并结合 Redux Toolki…

HarmonyOS 输入框组件:TextInput 和 TextArea 深度解析

输入框组件是移动端开发中最常见的组件之一&#xff0c;常用于响应用户的输入操作&#xff0c;比如评论区的文本输入、聊天框的消息输入、表单内容填写等场景。在 HarmonyOS 中&#xff0c;TextInput 和 TextArea 分别用于单行和多行输入操作。除此之外&#xff0c;它们还可以与…