​

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

文章目录

• 链表OJ题(七)
• • 7. 链表的回文结构
  • • 思路：
• 7.总结：

上一篇链表OJ题链接：【链表OJ题(六)】链表分割

链表OJ题(七)

7. 链表的回文结构

链接：OR36 链表的回文结构

描述：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

示例：
测试样例：1->2->2->1
返回：true

思路：

链表的回文结构:是从前向后遍历的元素和从后向前遍历的元素遍历到中间位置相等

如果不加空间复杂度为O(1)的限制的话，那么我们可以创建一个数组，然后遍历链表，将链表中元素放到数组中，从数组前后开始遍历，判断是否是回文结构。

但是这里已经给定了要求，那我们便要重新设计一个方法。
我们找到中间节点 mid，然后将 mid 开始的链表反转，将这个链表的起始节点给定为reHead，然后奇偶情况遍历链表。展开说明：
我们假定 reHead 已经反转，给定 curR来遍历 reHead，给定 curA 遍历 原链表 。

原链表为 奇数个节点：curA、curR 同时开始走， reHead 先走完，当 curA 走到 reHead 的 前一个节点 时，并不会走到 rehead 。因为原链表的结构并没有改变，所以会走到原链表的下一个位置。所以不用担心 reHead 反转后链表表面上改变，而导致回文结构辨识不出的情况。

原链表为 偶数个节点：curA、curR同时开始走，reHead先走完。这里由于 reHead 前和从 reHead 开始的节点个数相等，所以也就不需要担心。

结论：无论奇数偶数，只要 curA 和 curR 中有一个走到空就停止。

归纳一下这里的步骤： 找中心节点 -> 反转中心节点开始的链表 -> 迭代判断。

非常巧的是，之前博客中已经写过了前两步——链表的中心节点、反转链表，所以直接CV即可

注意：C++兼容C的语法，所以用C的语法写完全可以。

代码：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*///找中间节点
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast, *slow;fast = slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
//反转链表
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;struct ListNode* newNode = NULL;while (cur){struct ListNode* next = cur->next;// 头插cur->next = newNode;newNode = cur;// cur迭代cur = next;}return newNode;
}class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* mid = middleNode(A);struct ListNode* rHead = reverseList(mid);// A和rHead一般不会直接使用，拷贝一份struct ListNode* curA = A;struct ListNode* curR = rHead;while (curA && curR){if (curA->val != curR->val){return false;}curA = curA->next;curR = curR->next;}return true;}
};

7.总结：

今天我们分析并完成链表的回文结构这道链表OJ题目，了解了一个新的思路–找到中间节点 mid，然后将 mid 开始的链表反转，将这个链表的起始节点给定为reHead，然后奇偶情况遍历链表来判断，同时也复习链表的中心节点、反转链表这两个思路，在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~