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-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?