我把函数分离出来,把列表倒过来,求出它的长度,如果是回文,就求出它的回文。
int length(struct ListNode* head){
if(head == NULL)
return 0;
else
return (1+length(head->next));
}
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* prev = NULL;
struct ListNode* next = NULL;
struct ListNode* curr = head;
while(curr!=NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr=next;
}
return prev;
}
bool isPalindrome(struct ListNode* head){
int n = length(head);
struct ListNode* curr = NULL;
if(n%2==0){
int a=n/2;
curr = head;
while(curr!=NULL && a!= 0){
a--;
curr = curr->next;
}
}
else{
int a=n/2 + 1;
curr = head;
while(curr!=NULL && a!= 0){
a--;
curr = curr->next;
}
}
struct ListNode* node = reverseList(curr);
while(curr!=NULL && head!=NULL){
if(curr!=head)
return false;
curr = curr->next;
head = head->next;
}
return true;
}
我一直在尝试解决LeetCode中的问题“234.回文链表”,我以为我找到了解决方案,但由于某种原因,函数在应该返回true的情况下返回false。我试图找到错误,但我不能。
1条答案
按热度按时间vtwuwzda1#
您的程式码中有两个问题:
1.虽然你声明
node
是反向列表的头部,但是后面的循环并不使用node
,而是继续使用curr
,它现在是反向列表的尾部。相反,你应该在循环中使用node
,或者(节省空间)将反向列表赋值给curr
。1.比较
curr!=head
将始终为true。您应该比较节点的val
成员,而不是它们的地址。因此,请按如下方式更正相关部分: