Exemple de code d'implémentation du palindrome de chaîne Java

Ce que cet article vous apporte est un exemple de code sur l'implémentation du palindrome de chaîne Java. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

String Palindrome

Comment déterminer si une chaîne est une chaîne palindrome ? Je pense que vous auriez dû en entendre parler. Notre question de réflexion aujourd'hui est basée sur cette
question Version modifiée. Si la chaîne est stockée via une liste à chaînage unique, comment déterminer s'il s'agit d'une chaîne palindrome ? Avez-vous des
bonnes solutions ? Quelle est la complexité temporelle et spatiale correspondante ?

Idées :
1. Utilisez des pointeurs rapides et lents pour trouver le nœud du milieu
2 Tout en trouvant le nœud du milieu, copiez une liste chaînée dans l'ordre inverse du début vers le nœud du milieu précédent<.>3. Comparez si la liste chaînée précédente et la liste chaînée lente sont identiques

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;


    }
}

Meilleure complexité temporelle :

Le meilleur cas est un seul caractère ou une chaîne vide, la complexité temporelle est O(1)

Pire complexité temporelle :

Complexité temporelle de la recherche des nœuds intermédiaires n/2
Comparer la complexité temporelle de la taille n'est pas jusqu'à la fin pour comparer s'ils sont égaux, donc c'est n/2
La complexité temporelle finale du total est O(n)

Cet article est ici Pour un contenu plus passionnant, vous pouvez faire attention au

. Tutoriel vidéo Java sur le site PHP chinoisColonne !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!