我在练习一个基于单向链表的问题,看起来很简单。问题是如果给定的单向链表是回文,则返回真,否则返回假。 我首先通过遍历直到最后一个节点获得列表的长度然后将列表的所有值推送到一个向量,然后检查向量是否相同如果从最后一个节点遍历如果相同则返回真或返回假。
但是我得到这个错误说:
第 24 行:字符 24:运行时错误:在“struct ListNode”类型的空指针内访问成员(solution.cpp) 摘要:UndefinedBehaviorSanitizer:undefined-behavior prog_joined.cpp:33:24
class Solution {
public:
bool isPalindrome(ListNode* head) {
struct ListNode *temp;
int j,data,l=0,r;
vector <int> v;
temp=head;
while(temp!=NULL){//to get length of the linked list
j++;
temp=temp->next;
}
temp=head;
for(int i=0;i<j;++i){
data=temp->val;
v.push_back(data);
temp=temp->next;
}
r=v.size()-1;
while (l<=r){
if(v[l]!=v[r]) return false;
}
return true;
}
};
这是您问题的替代解决方案。试试这个让我知道:
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) {
return true; // empty list or single node list is a palindrome
}
// Find the middle of the linked list using slow and fast pointers
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
// Reverse the second half of the linked list
ListNode *prev = nullptr, *curr = slow->next;
while (curr) {
ListNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
// Check if the first and second half of the linked list are identical
ListNode *p1 = head, *p2 = prev;
while (p2) {
if (p1->val != p2->val) {
return false;
}
p1 = p1->next;
p2 = p2->next;
}
// Reconstruct the linked list by reversing the second half back
// to its original order before returning
curr = prev;
prev = nullptr;
while (curr) {
ListNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
slow->next = prev;
return true;
}
};