Java字符串回文实现的代码示例

字符串回文

如何判断一个字符串是否是回文字符串的问题，我想你应该听过，我们今天的思题目就是基于这个问题的改造版本。如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？你有什么好的解决思路呢？相应的时间空间复杂度又是多少呢？

思路：1.使用快慢指针来找到中间节点2.在找中间节点的同时复制一份反序的从开头到中间节点的链表prev3.比较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;       } }

最坏时间复杂度：查找中间节点时间复杂度n/2比较大小时间复杂度直到最后才比较出是否相等所以为n/2相加起来最后的时间复杂度为O(n)

本篇文章到这里就已经全部结束了，更多其他精彩内容可以关注PHP中文网的Java视频教程栏目！

以上就是Java字符串回文实现的代码示例的详细内容，更多内容请关注技术你好其它相关文章！