这篇文章给大家分享的是有关Java字符串回文的实现方法的内容。小编觉得挺实用的，因此分享给大家做个参考。一起跟随小编过来看看吧。
成都创新互联主要从事网站设计、网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务仪征,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108
字符串回文
如何判断一个字符串是否是回文字符串的问题，我想你应该听过，我们今天的思题目就是基于这个
问题的改造版本。如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？你有什么
好的解决思路呢？相应的时间空间复杂度又是多少呢？
思路：
1.使用快慢指针来找到中间节点
2.在找中间节点的同时复制一份反序的从开头到中间节点的链表prev
3.比较prev链表和slow链表是否相同
代码：
package me.study.algorithm;
/**
* public class LinkNode {
*
* char val;
*
* LinkNode next;
*
* public LinkNode() {
* }
*
* public LinkNode(char val) {
* this.val = val;
* }
* }
*/
public class StringBack {
public boolean clac(LinkNode head) {
if (head.next == null && head.next == null){
return true;
}
LinkNode prev = null;
LinkNode slow = head;
LinkNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
LinkNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
if (slow.val != prev.val) {
return false;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
}最好时间复杂度：
最好的情况就是单个字符或者空字符串，时间复杂度为O(1)
最坏时间复杂度：
查找中间节点时间复杂度n/2
比较大小时间复杂度直到最后才比较出是否相等所以为n/2
相加起来最后的时间复杂度为O(n)
感谢各位的阅读！关于Java字符串回文的实现方法就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到吧！
