链表的回文结构
文章目录
- 链表的回文结构
-
- 一、题目
- 二、思路分析
一、题目
?题目指路：OR36 链表的回文结构_牛客题霸_ 牛客网 (nowcoder.com)
?描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900
?测试样例：
1->2->2->1
返回：true
二、思路分析
??我们需要找到中间的数的地址
?存在两种情况：
- ?偶数个节点
- ?奇数个节点
??fast->next = NULL 或 fast = NULL 结束循环??
?找到中间点之后，翻转之后的节点链接
??可以参考之前的文章：【LeetCode·单链表.206】反转链表??
翻转链表至下图样子
- ?奇数比较：
- ?偶数比较：
??方块是比较顺序??
?代码如下?
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {ListNode* slow = A;ListNode* fast = A;while(fast->next && fast){fast = fast->next->next;slow = slow->next;}ListNode* cur = slow;ListNode* tail = NULL;ListNode* newnode = NULL;while(cur){newnode = cur;cur = cur->next;newnode->next = tail;tail = newnode;}ListNode* curA = A;ListNode* curR = newnode;while(curA && curR){if(curA->val != curR->val){return false;}curA = curA->next;curR = curR->next;}return true;}
};