​LeetCode刷题实战234:回文链表

沙海
沙海
沙海
994
文章
2
评论
2021年4月9日12:49:57
评论
5 2196字阅读7分19秒
摘要

速读摘要

速读摘要

为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选~!先进后出,把节点压入栈中,到中间节点后,依次从栈中弹出节点,与后半部分的节点值对比即可。的空间复杂度下,只能选择操作原链表来完成该题。利用迭代法反转链表,时间复杂度为O(n),空间复杂度为O(1),所以符合要求。然后从原链表头节点与反转后后半部分链表头节点开始对比值即可。

原文约 2260 | 图片 1 | 建议阅读 5 分钟 | 评价反馈

​LeetCode刷题实战234:回文链表

程序IT圈

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 回文链表,我们先来看题面:

https://leetcode-cn.com/problems/palindrome-linked-list/

Given the head of a singly linked list, return true if it is a palindrome.

请判断一个链表是否为回文链表。

示例

示例 1:输入: 1->2输出: false示例 2:输入: 1->2->2->1输出: true进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

解题

https://www.imooc.com/article/289808

首先是寻找链表中间节点,这个可以用快慢指针来解决,快指针速度为2,慢指针速度为1,快指针遍历完链表时,慢指针刚好走到中间节点(相对)。

然后是判断是否是回文链表:

不考虑进阶要求的话,方法千千万。可以把前半部分暂存入新的数组、链表、哈希表等等数据结构,然后依次倒序取出,与后半部分链表每个节点的值对比即可。更简单的是直接用数据结构 - 栈,先进后出,把节点压入栈中,到中间节点后,依次从栈中弹出节点,与后半部分的节点值对比即可。

直接思考进阶要求,在 O(1) 的空间复杂度下,只能选择操作原链表来完成该题。好在这道题只要求返回布尔值,即便把原链表改变了也不用担心。我们可以将链表后半部分 反转,利用迭代法反转链表,时间复杂度为 O(n),空间复杂度为 O(1),所以符合要求。然后从原链表头节点 与 反转后后半部分链表头节点开始对比值即可。

class Solution {    public boolean isPalindrome(ListNode head) {        ListNode fast = head;        ListNode slow = head;        if (fast == null || fast.next == null) return true;        while (fast.next != null && fast.next.next != null) {            fast = fast.next.next;            slow = slow.next;        }        ListNode newHead = reverseList(slow.next);        while (newHead != null) {            if (head.val != newHead.val) return false;            head = head.next;            newHead = newHead.next;        }        return true;    }  //反转链表函数--详情请看前文    private ListNode reverseList(ListNode head) {        if (head.next == null) return head;        ListNode pre = null;        ListNode tmp;        while (head!= null) {            tmp = head.next;//tmp暂存当前节点的下一个节点            head.next = pre;//当前节点下一个指向pre            pre = head;//刷新pre            head = tmp;//刷新当前节点为tmp        }        return pre;    }}

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-220题汇总,希望对你有点帮助!

LeetCode刷题实战221:最大正方形

LeetCode刷题实战222:完全二叉树的节点个数

LeetCode刷题实战223:矩形面积

LeetCode刷题实战224:基本计算器

LeetCode刷题实战225:用队列实现栈

LeetCode刷题实战226:翻转二叉树

LeetCode刷题实战227:基本计算器 II

LeetCode刷题实战228:汇总区间

LeetCode刷题实战229:求众数 II

LeetCode刷题实战230:二叉搜索树中第K小的元素

LeetCode刷题实战231:2的幂

LeetCode刷题实战232:用栈实现队列

LeetCode刷题实战233:数字 1 的个数

​LeetCode刷题实战234:回文链表

继续阅读
weinxin
资源分享QQ群
本站是一个IT技术分享社区, 会经常分享资源和教程; 分享的时代, 请别再沉默!
沙海
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: