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

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作为返回值。但至少当head是null时，您不会访问->next

• 它改变了给定的列表。这不是很好。调用方预计不会发生这种情况，并且可能需要原始列表用于其他目的，即使在调用isPalindrome之后也是如此。

• 它很慢。它的时间复杂度是二次型的。如果这是编码挑战的一部分，那么测试数据可能很大，并且函数的执行可能会超过分配的时间。

使用堆栈确实是一种解决方案，但感觉像是作弊：然后您还可以将整个列表转换为一个数组，并使用其直接寻址功能测试该数组是否为回文。

您可以使用以下列表来完成此操作：

1. 计算列表中的节点数
2. 使用它来标识列表后半部分的第一个节点。如果节点数为奇数，则设其为中心节点之后的节点
3. 在后半部分应用列表反转算法。现在您有两个较短的列表
4. 比较这两个列表中的值是否相等(如果有，则忽略中心节点(。记住结果(假或真(
5. 重复步骤3，以便回滚反转，并且列表恢复到其原始状态
6. 返回在步骤4中找到的结果

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