如何使这段用于检测链表中回文的代码涵盖所有情况？

Question

所以，我正在解决这个在链表中检测回文的问题。我想出了以下解决方案：

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode temp=head;
        boolean [] arr = new boolean[10];
        int count=0;
        if(head==null) return false;
        while(temp!=null)
        {
            if(arr[temp.val]==false)
                arr[temp.val]=true;
            
            else
                arr[temp.val]=false;
            temp=temp.next;
        }
        for(int i=0;i<10;i++)
        {
            if(arr[i]==true)
                count++;
        }
        if(count<2)return true;
        return false;

    }

现在，据我所知，此解决方案背后的逻辑是正确的，但它在以下情况下失败：[1,0,0]、[4,0,0,0,0] 等。如何我克服了吗？（请不要用更短的方法回复我想知道为什么在某些情况下失败的原因。）

Answer 1

首先欢迎来到 Whosebug！

由于这个问题的解决方案非常简单，所以我有义务告诉您，使用辅助堆栈的解决方案不仅易于实现而且易于理解。但是既然你问过为什么你的代码在某些情况下会失败，我会先回答这个问题。您的代码特别是计算奇数的位数。

尽管这似乎是检测回文串的方法，但请注意，在您的代码中，看起来像 1 -> 1 -> 0 -> 0 的链表也被视为回文串，因为计数是总是小于 0.

您的解决方案可以告诉我们是否可以在给定一组数字的情况下创建回文。假设问题是“给定一个链表，告诉我你是否可以重新排列它来创建回文”，但它不适用于“这个链表是回文吗”。

如何使这段用于检测链表中回文的代码涵盖所有情况？

How do I make this code for detecting palindrome in a Linked List cover all cases?

linked-list

data-structures

singly-linked-list