链表面试题6之回文结构

 经过前几道题的铺垫，那么我们也是来到了链表的第六关。这也是一道非常经典的题目。

目录

逆置法

数组法

---

那么对于这道题目，我们要判断回文结构，实际上就是判断链表对不对称。这种类型的题目我们好像在哪里见过，对了，就是在字符串那里。那这里咱们可不可以也用一个双指针法，然后一个从头遍历，一个从尾开始遍历？？当然是不可以的，因为链表的物理结构就规定了，链表只能从头开始遍历。

那么我们想到这里的话，也自然会想到，我现在的难点是尾端无法向前遍历，有什么办法能让我从尾端向前面遍历呢？这我们就灵机一动，把链表部分逆置不就好了？

那么由此我们就能得出第一种方法

逆置法

思路：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->nextbreak;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;}
};

好了，这道题就讲到这里

如果你觉得对你有帮助，可以点赞关注加收藏，感谢您的阅读，我们下一篇文章再见。

一步步来，总会学会的，首先要懂思路，才能有东西写。