Code example of Java string palindrome implementation

This article brings you code examples about Java string palindrome implementation. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

String Palindrome

How to determine whether a string is a palindrome string? I think you should have heard of it. Our topic today is based on this
question Modified version. If the string is stored through a singly linked list, how to determine whether it is a palindrome string? Do you have any
good solutions? What is the corresponding time and space complexity?

Ideas:
1. Use fast and slow pointers to find the intermediate node
2. While finding the intermediate node, copy a reverse linked list from the beginning to the intermediate node prev
3. Compare whether the prev linked list and slow linked list are the same

Code:

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;


    }
}

Best time complexity:
The best case is a single character or an empty string, the time complexity is O( 1)

Worst time complexity:
Time complexity of finding intermediate nodes is n/2
Comparing size time complexity is not until the end to compare whether they are equal, so it is n/2
phase The total time complexity is O(n)

This article is all over here. For more exciting content, you can pay attention to the Java Video Tutorial column of the PHP Chinese website. !

The above is the detailed content of Code example of Java string palindrome implementation. For more information, please follow other related articles on the PHP Chinese website!