Java字符串回文实现的代码示例
程序员文章站
2022-03-02 18:57:01
...
本篇文章给大家带来的内容是关于Java字符串回文实现的代码示例,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
字符串回文
如何判断一个字符串是否是回文字符串的问题,我想你应该听过,我们今天的思题目就是基于这个
问题的改造版本。如果字符串是通过单链表来存储的,那该如何来判断是一个回文串呢?你有什么
好的解决思路呢?相应的时间空间复杂度又是多少呢?
思路:
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)
本篇文章到这里就已经全部结束了,更多其他精彩内容可以关注PHP中文网的Java视频教程栏目!
以上就是Java字符串回文实现的代码示例的详细内容,更多请关注其它相关文章!
上一篇: Java是前端还是后端?
下一篇: Servlet生命周期的介绍