链表的回文结构（详解）

本文主要是介绍链表的回文结构（详解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链表的回文结构（详解）

题目：

链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1
返回：true

思路：

我们想要通过对比链表的前一半和链表的后一半是否相同来判断是否为回文结构
那我们就要找到中间节点，也就是快慢指针法
不仅如此，我们还要通过prev来记录slow的前一个节点，这样我们在后面需要对prev进行断联，我们才得到该节点
这个时候将slow节点和之后的节点进行逆置，创建一个新链表，让slow节点和之后的节点依次头插到新链表当中
逆置完链表之后，要记得让slow节点之前的节点断联，也就是prev->next = NULL
然后就是遍历原链表判断两个链表的val值是否相等，不相等返回false，相等返回true

代码：

struct ListNode {int val;struct ListNode* next;
};typedef struct ListNode ListNode;
bool chkPalindrome(ListNode* A)
{// 创建快慢指针，去找到链表的中间节点ListNode* slow, * fast;slow = fast = A;// 创建一个prev指针去专门指向slow的前一个节点 最终找到的是中间节点的前一个节点ListNode* prev = A;// 找到中间节点  2slow = fastwhile (fast && fast->next){prev = slow; // 指向slow的前一个节点slow = slow->next;fast = fast->next->next;}// 此时slow就是A链表的中间节点// 这个时候我们逆置slow节点后面的节点// 如果和slow节点前面的节点一样，那就是回文结构// 创建新链表ListNode* newhead = NULL;// 将slow节点及以后的节点逆置// 也就是让后面的节点依次头插到新链表中ListNode* pcur = slow;while (pcur){ListNode* next = pcur->next; // 让next记载pcur的下一个节点pcur->next = newhead; // 让pcur头插到新链表中newhead = pcur; // 更新第一个节点pcur = next; // 让pcur继续向后遍历}// 走到这里 slow及slow后面的节点都逆置完毕了// 但是有一个需要注意的地方，我们的slow的前一个节点仍然指向的是slow节点// 但是我们又新创建了一个逆置链表，那么prev此时的next指针指向的就是逆置链表的尾节点// 因此我们需要将prev不在指向slow节点，而是NULLprev->next = NULL;// 这个时候我们去判断 新链表是否和 A链表第一个节点到slow节点之前相等ListNode* cur = A;while (cur){// 判断原链表和新链表的val值是否相同if (cur->val != newhead->val)return false; // 不同就返回falsecur = cur->next; //相同就继续往下走newhead = newhead->next;}// 走到这里说明是回文结构了return true;
}