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.