✨✨所属专栏：LeetCode刷题专栏✨✨

✨✨作者主页：嶔某✨✨

题目描述：

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

就比如：1->2->3->2->1就是回文链表，1->2->3->1->2不是回文链表。

示例代码：

class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code here
};

 分析：

这里我们得到解法是先找到链表的中间节点，之后将中间节点后面的节点全部逆置。之后再从mid节点和链表头节点开始遍历、判断值是否相同，以mid节点和链表头节点都不为空为循环条件。

 所以这里我们先要写出找中间节点的代码：

以前做过类似的题《快慢指针》。快指针一次走两步，慢指针一次走一步。最终慢指针会停在中间节点处。

 注意：这里while循环的条件不能把fast->next放在前面，要先判断的fast不为空，再判断fast的下一个节点是否为空。否则会导致空指针的解引用。

struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast = head, *slow = head;while(fast && fast->next) {slow = slow->next;fast  = fast->next->next;}return slow;
}

链表逆置代码：

struct ListNode* ReverseList(struct ListNode* head ) {struct ListNode* pcur = head;struct ListNode* prev = NULL;while(pcur){struct ListNode* tmp = pcur->next;pcur->next = prev;prev = pcur;pcur = tmp;}    return prev;
}

 主代码：

class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* mid = middleNode(A); struct ListNode* rmid = ReverseList(mid);while(A && rmid){if(A->val != rmid->val)return false;A = A->next;rmid = rmid->next;}return true;}
};

本期博客到这里就结束了，如果有什么错误，欢迎指出，如果对你有帮助，请点个赞，谢谢！