1. 链表的回文结构
1.1 题目说明
对于一个链表，请设计一个时间复杂度为 O(n)，额外空间复杂度为 O(1) 的算法，判断其是否为回文结构。
给定一个链表的头指针 A，请返回一个 bool 值，代表其是否为回文结构。保证链表长度小于等于 900。
测试样例：
1->2->2->1
返回：true
1.2 题目分析
一、题目要求
- 时间复杂度为 O(n)：意味着算法的执行时间与输入规模呈线性关系。
- 额外空间复杂度为 O(1)：除输入所占用的空间外，算法所使用的额外空间保持在一个常量级别。
- 判断链表是否为回文结构：回文结构是指正序和逆序读取内容相同。
- 给定链表的头指针 A，返回一个 bool 值表示是否为回文结构，且链表长度小于等于 900。
二、知识点关联
- 链表：链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
- 栈：栈是一种后进先出的数据结构，可以用来辅助判断链表是否为回文结构。
三、解题思路探讨 由于时间复杂度要求为 O(n)，可以考虑一次遍历链表完成判断。额外空间复杂度为 O(1)，不能使用额外的数据结构来存储整个链表，需要巧妙地利用指针和变量来进行判断。 可以使用快慢指针的方法找到链表的中间位置，然后对后半部分链表进行反转，再与前半部分进行比较来判断是否为回文结构。具体步骤如下：
- 使用两个指针，一个快指针每次移动两步，一个慢指针每次移动一步，当快指针到达链表末尾时，慢指针正好位于链表的中间位置。
- 如果链表长度为奇数，慢指针正好指向中间节点，此时可以忽略中间节点，继续对后半部分链表进行反转。
- 反转后半部分链表后，使用两个指针分别从链表的头部和中间位置（或中间位置的下一个节点）开始同时遍历，比较对应节点的值是否相等。
四、注意事项
- 处理链表长度为奇数的情况时，要正确地找到中间节点并进行后续的操作。
- 在反转链表后半部分时，要注意保存链表的结构，以便在判断完成后恢复链表的原始状态（如果需要的话）。
- 考虑链表为空或只有一个节点的特殊情况，这种情况下链表显然是回文结构。
