经过前几道题的铺垫，那么我们也是来到了链表的第六关。这也是一道非常经典的题目。
目录
那么对于这道题目，我们要判断回文结构，实际上就是判断链表对不对称。这种类型的题目我们好像在哪里见过，对了，就是在字符串那里。那这里咱们可不可以也用一个双指针法，然后一个从头遍历，一个从尾开始遍历？？当然是不可以的，因为链表的物理结构就规定了，链表只能从头开始遍历。
那么我们想到这里的话，也自然会想到，我现在的难点是尾端无法向前遍历，有什么办法能让我从尾端向前面遍历呢？这我们就灵机一动，把链表部分逆置不就好了？
那么由此我们就能得出第一种方法
逆置法
思路：1.先找到中间节点,
2.从中间节点以后开始逆置
3.然后从中间节点向后迭代
4.如果是回文,返回true,否则返回false
那这里我把代码贴一下
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));//哨兵结点
dummy->next = A;
ListNode*fast = dummy;
ListNode*slow = dummy;
while(fast && fast->next) //获取中间结点
{
fast = fast->next->next;
slow = slow->next;
}
ListNode* cur = slow->next; //反转链表
ListNode* next = cur->next;
ListNode* pre = slow;
slow->next = NULL; //防止形成环！！！！！
while(1)
{
cur->next = pre;
pre = cur;
if(next == NULL) //注意判断的是next而不是cur->next
break;
cur = next;
next = cur->next;
}
ListNode* head = A;
ListNode* tail = cur;
while(tail != slow)
{
if(head->val != tail->val)
return false;
tail = tail->next;
head = head->next;
}
return true;
}
};当然，这里找中间节点涉及到一个快慢指针的问题。
数组法
没错，想到了逆置，我们在实现的过程中也会出现一个问题，那就是原链表和逆置后的链表的输出结果，需要我们去存储。那么这里我们就想，能不能用数组优化一下，使得我们不用两个链表的双线操作。
那么他来了！
思路：直接创建一个int a[900]的数组。储存输出的数据，再逆序访问输出比较。
这样真的可行吗？？？
注意，这里的空间复杂度已经是O（n）了，嗯？为什么是O（n）呢？我创建的数组空间不是有限个空间吗？没错，这里的空间复杂度就是O（1）。这种方法是可行的。那什么时候是O（n）呢？
我们在动态数组的时候就是O（n），是空间会随着你所给数据的多少而扩容不确定的才会是O（n)
但是我这里已经明确给出了链表长度不超过900，而我不在乎空间的浪费，就定义为a[900]。这是常数，下面是两种情况会给出O（n）的空间。我
// 动态分配空间（与输入规模相关）
int* a = new int[n];
// 可变长度容器（隐式依赖输入规模）
std::vector<int> a(n); 具体代码：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
int buffer[900];
int length = 0;
// 步骤1：存储链表数据到数组
ListNode* curr = A;
while (curr && length < 900) {
buffer[length++] = curr->val;
curr = curr->next;
}
// 步骤2：双指针回文校验
int left = 0, right = length - 1;
while (left < right) {
if (buffer[left] != buffer[right]) {
return false;
}
left++;
right--;
}
return true;
}
};好了，这道题就讲到这里
如果你觉得对你有帮助，可以点赞关注加收藏，感谢您的阅读，我们下一篇文章再见。
一步步来，总会学会的，首先要懂思路，才能有东西写。