234. 回文链表 (JAVA)
2021/4/9 22:55:13
本文主要是介绍234. 回文链表 (JAVA),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
思路:改变前半部分或者后半部分List的next指针。由于改变前半部分只需要一次遍历(用快、慢指针就能实现在第一次遍历的时候把前半部分的next指针反转)
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { ListNode fast = head, slow = head, pre = null, tmp; while(fast.next!=null) { fast = fast.next.next; tmp = slow.next; slow.next = pre; pre = slow; slow = tmp; if(fast == null){ //双数 return check(pre, slow); } } //单数 return check(pre, slow.next); } private boolean check(ListNode l1, ListNode l2){ if(l1 == null) return true; if(l1.val != l2.val) return false; return check(l1.next, l2.next); } }
这篇关于234. 回文链表 (JAVA)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署