Palindrome mit Linked List in Java

Aufrufe: 238     Aktiv: 09.01.2021 um 22:14

0

Hallo zusammen

ABBA = ABBA

Palindrom. Ein Wort ist ein Palindrom, wenn sein Gegenteil gleich sich selbst ist. Zum Beispiel: ABBA ist ein Palindrom. Eine Möglichkeit, ein Wort in einem Computer darzustellen, besteht darin, dass man eine einfach verkettete Liste, in der für jeden Buchstaben ein Listenelement vorhanden ist. ABBA wird zum Beispiel dargestellt durch die einfach verkettete Liste dargestellt. Entwerfen und analysieren Sie einen Algorithmus, der, wenn ein Zeiger auf den Kopf einer einfach verknüpften Liste die ein Wort repräsentiert, JA ausgibt, wenn das Wort ein Palindrom ist, und sonst NEIN. Um die volle Punktzahl zu erreichen, sollte Ihr Algorithmus in linearer Zeit laufen und keine anderen Datenstrukturen als einfach verkettete Listen verwenden, d. h. keine Arrays, Stapel, Warteschlangen.

Meine Idee

Zu der vorhanden Linked List erstelle ich noch eine, welche ebenfalls dieselben Wörter speichert, welche Palindrome sind.

Was ich nicht verstehe, wenn ich die Buchstaben einzeln abspeichere muss ich doch irgendwie verfizieren, ob es sich um ein Palindrome handelt oder nicht. Dann muss ich doch irgendwo den Wert bzw. Anzahl der Buchstaben abspeichern oder nicht? Wie programmiert man so etwas in Java?

Vielen Dank

Diese Frage melden
gefragt

Student, Punkte: 64

 
Kommentar schreiben
1 Antwort
0
public static boolean isPalindrome(ListNode head) {
    // list with zero, one or two nodes
    if (head == null || head.next == null) return true;
    else if (head.next.next == null) return head.val == head.next.val;

    int len = len(head);
    ListNode mid = getMidNodeOfList(head);
    ListNode reversed = reverseList(len%2==0 ? mid : mid.next);
    while (head != null) {
        if (head == mid) return true;
        else if (reversed == null) return false;
        else if (head.val != reversed.val) return false;

        head = head.next;
        reversed = reversed.next;
    }
    return true;
}

private static int len(ListNode head) {
    int len = 0;
    while (head != null) {
        head = head.next;
        len++;
    }
    return len;
}

private static ListNode getMidNodeOfList(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast == null) break;
    }
    return slow;
}

private ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode tmp_next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tmp_next;
    }
    return prev;
}

Der Algorithmus läuft mit O(n), also linear und mit O(1) Speicherkomplexität. Er besteht aus insgesamt 3 Schritten: Suche den mittleren Knoten der Liste, "reverse" diese Teil-Liste (von mid bis zum Ende), also im Endeffekt einfach die Teil-Liste umdrehen und als letztes die daraus entstandene Liste mit der Liste vom Anfang (head) bis zur Mitte prüfen, ob alle Zeichen am jeweiligen Index gleich sind --> Wenn ja, dann ist es ein Palindrom, sonst nicht.

Diese Antwort melden
geantwortet

Schüler, Punkte: 385

 

Kommentar schreiben