问题是检查给定的链表是否为回文。请告诉我我做错了什么？

Question

我了解其他方法，例如使用堆栈和反转链表的后半部分。但是，我的方法有什么问题。

* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
   public boolean isPalindrome(ListNode head) {
       if(head.next==null){return true;}
       
       while(head!=null){
           ListNode ptr=head, preptr=head;
           while(ptr.next!=null){ptr=ptr.next;}
           if(ptr==head){break;}
           while(preptr.next.next!=null){preptr=preptr.next;}
           
           if(head.val==ptr.val){
               preptr.next=null;
               head=head.next;
           }
           else{return false;}   
       }
       
       return true;
       
   }
}```

Answer 1

关于您的解决方案可以说如下：

如果 head 为 null，则失败并出现异常。为避免这种情况，您可以只删除第一个 if 语句。这种情况不需要单独处理。当列表是单个节点时，第一次迭代将执行 break，因此您将获得 true 作为 return 值。但至少当 head 是 null
时你不会访问 ->next
它改变了给定的列表。这不是很好。调用者不会预料到会发生这种情况，并且即使在调用 isPalindrome.
之后也可能需要原始列表用于其他目的
速度很慢。它的时间复杂度是二次的。如果这是编码挑战的一部分，那么测试数据可能会很大，您的函数的执行可能会超过分配的时间。

使用栈确实是一种解决方案，但感觉有点作弊：那你不妨把整个列表转成一个数组，用它的直接寻址能力来测试这个数组是否是回文

您可以只使用列表来执行此操作，如下所示：

计算列表中的节点数
用它来识别列表后半部分的第一个节点。如果节点数为奇数，则设为中心节点之后的节点。

在下半场应用列表反转算法。现在你有两个较短的列表。

比较这两个列表中的值是否相等（如果有则忽略中心节点）。记住结果（假或真）

重复第 3 步，使反转回滚，列表回到其原始状态。

Return 在步骤 4 中找到的结果。

这需要线性时间，因此对于更大的列表，这应该优于您的解决方案。

问题是检查给定的链表是否为回文。请告诉我我做错了什么？

The question is to check whether the given linkedlist is palindrome. Please tell what am I doing wrong?

linked-list

palindrome